21. Amicable numbers

1. 개요

문제는 이곳에서 확인할 수 있다. 자연수 $n$보다 작으면서 $n$을 나누어 떨어지게 하는 수를 proper divisor라고 하자. 그리고 $d(n)$을 $n$에 관한 proper divisors의 합이라고 정의하자. 이때 서로 다른 $a$와 $b$에 대하여 $d(a)=b$, $d(b)=a$의 관계가 있을 때 $a$와 $b$를 amicable numbers라고 한다. 예를 들어, $d(220)=284$, $d(284)=220$이므로 220과 284는 amicable numbers이다. 10000보다 작은 amicable numbers의 합을 구하는 것이 문제의 목표이다.

2. Ver 1.0

$d(n)$을 정의할 때, 처음에는 소수를 사용하는 방법을 생각했다. 그런데 포스팅을 위하여 다시 보니 불필요하게 복잡한 구현인 듯 하여 좀 더 쉬운 방법을 선택하였다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

# -*- coding: utf-8 -*- import math as m   # 1. Define d(n) def d(n):     lim = m.sqrt(n)     divisor = 2     result = 1     while divisor <= lim:         quotient, remainder = divmod(n, divisor)           if remainder == 0:             result += (divisor + quotient)         divisor += 1       if (divisor - 1) == lim:         result -= divisor       return result   # 2. Evaluate the sum of all the amicable numbers under 10000. d_set = dict() for n in range(2, 10000):     d_set[n] = d(n)   result = 0 for k, v in d_set.items():     if v in d_set and k != v and d_set[v] == k:         print('Amicable number: ', k, v)         result += k   print(result)

답은 31626이다.