[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))
접기

댓글 1개:

  1. trackback from: Project Euler
    몇일 전 올린 KATE관련 내용의 관련글이라고 링크가 걸린 Bluekyu님의 블로그를 구경하다 Project Euler에 관심이 갔다. 간단하게 요약하자면, 현재까지, 제공되는 299개의 수학 문제가 있고, programming skill로 해결을 보고 정답을 확인하는, 그런거다. 쿨럭. - 직접 방문해보면 한눈에 들어온다 - 어카운드 생성시 프로파일 작성내역 중, Language 선택부분이 있는데, 그에 따른 관련 스탯 링크도 존재한다 연산관련 코..

    답글삭제

크리에이티브 커먼즈 라이선스