[Project Euler] Problem 21

원문: Problem 21

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.

d(n)을 n 의 진약수들(n보다 작고 n을 나누는 수들)의 합으로 정의하자.
a b 일 때 d(a) = b 이고 d(b) = a 이면, a와 b는 친화쌍이고 a와 b 각각을 친화수라고 한다.

예를 들어, 220의 진약수는 1, 2, 4, 5, 10, 11 20, 22, 44, 55, 110 이다. 그러므로 d(220) = 284 이다. 284의 진약수는 1, 2, 4, 71, 142 이므로 d(284) = 220 이다.

10000 미만의 모든 친화수들의 합을 구하여라.

Python

지난번에 사용했던 인수분해 코드를 이용했다.

>>> def factor(n) :
    if n <= 0 :
        return {}
    f = {}
    for k in [2,3,5,7,11,13,17,19,23,29,31,37,41] :
        while not (n % k) :
            f[k] = f.setdefault(k, 0) + 1
            n //= k
    while n != 1 :
        if k > n**0.5 :
            f[n] = 1
            break
        while not (n % k) :
            f[k] = f.setdefault(k, 0) + 1
            n //= k
        k += 2
    return f

>>> def check(a) :
    def sum_divisor(n) :
        i = 1
        for key, value in factor(n).items() :
            i *= sum(key**index for index in range(value+1))
        i -= n
        return i
    b = sum_divisor(a)
    if sum_divisor(b) == a and a != b :
        return True
    else :
        return False

>>> sum(k for k in range(2, 10000) if check(k))

접기