[Euler Project] Problem 21 using Python

Euler Project 21번 문제는 10000 이하의 Amicable numbers를 구하는 문제이다. 특정 수 a 의 약수의 합을 b라고 하고, 해당 관계를

d(a) = b

로 나타낼 때, d(a) = b and d(b) = a 일 경우 a와 b는 amicable numbers다.

 

단순히 모든 경우를 계산해도 수 초 내에 계산이 가능하다.

 

 

"""
Euler Project 21: Amicable numbers

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).

If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair
and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110;
therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000
"""

import numpy as np
dynamic = [0]           # saving sum of divisors for each number
amicable = []           # append amicable

def get_all_divisor(n):
    # throw error if type is not appropriate
    assert type(n) == type(1)

    res = []
    # n//2 + 1 since possible minimum value is 2
    for i in range(1, n//2 + 1):
        # if properly divided, append the value
        if n % i == 0:
            res.append(i)

    # save data to dynamic and return summed value
    ret = np.sum(res)
    dynamic.append(ret)
    return int(ret)


if __name__ == '__main__':
    # iterate over 1 to 9999
    for i in range(1, 10000):
        sm = get_all_divisor(i)

        # for the amicable pair, only check for bigger one >> small one
        if sm < i and dynamic[sm] == i:
            amicable.append(i)
            amicable.append(sm)

    print(amicable)
    print(np.sum(amicable))