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는 친화수의 쌍(amicable pair)이며 a와 b는 각각 친화수(amicable numbers)이다.
예를 들어, 220의 진약수는 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 100이므로 d(220)=284이다. 284의 진약수는 1, 2, 4, 71, 142이므로 d(284)=220이다.
10000 이하의 모든 친화수의 합계를 구하라.
--------------------------------------------------------------------------
약수를 구하고, 진약수의 합계를 구하는 함수를 만들고 나면 간단히 해결 가능한 문제이다.
1부터 10000까지 진약수를 구하면서, 진약수의 합계인 d(a)가 a보다 큰 경우에만 검사하도록 하여(d(a)가 작은 경우는 이미 검증했을 것이므로) 실행성능도 개선하고, 같은 수를 2번 계산하지 않도록 하였다.