Project Euler 21
Question:
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.
문제:
n의 약수들 중에서 자신을 제외한 것의 합을 d(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 입니다.
따라서 220과 284는 친화쌍이 됩니다.10000 이하의 친화수들을 모두 찾아서 그 합을 구하세요.
Solution:
from sympy import divisors div = dict() for i in range(1,10000): div[i] = sum(divisors(i)) - i pair = list() for i in range(1,10000): if div[i] < 1 or div[i] > 9999: pass elif i == div[div[i]] and i != div[i]: pair.append([i,div[i]]) div[i] = 0 print(sum(map(sum,pair)))
div dictionary 에 자신을 제외한 약수들의 합을 저장해준다
약수의 합이 1이 안되거나, 10000 이상이면 판별을 건너뛰어준다.
조건을 만족하는지 확인한 후, pair 에 append 해준다
pair 에 순서가 다른 같은 쌍이 들어가는 걸 방지하기 위해 조건을 만족하면 0으로 만들어준다