오일러 프로젝트 21

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 이하의 친화수들을 모두 찾아서 그 합을 구하세요.

http://euler.synap.co.kr/prob_detail.php?id=21

접근

친화쌍인 수들을 찾아서 그 합을 구하는 문제이다. 친화수는 서로가 서로의 진약수의 합인 수들로, 이를 찾기 위해서는 약수의 합을 빠르게 찾는 방법을 결정하는 것이 중요하다. 사실 최대 크기가 10,000 밖에 되지 않으므로 제곱근 이하의 수로 모두 나눠보는 것이 가장 편하고 빠른 방법이 될 것이다.

자연수 n에 대해서 진약수의 합을 m 이라 할 때, m이 1만 이하의 수이고, m의 진약수의 합이 n이라면 둘은 조건을 만족한다. 그리고 n에 대해서 친화쌍인 m을 찾았다면 m에 대해서는 이 과정을 굳이 반복할 필요가 없다. 따라서 이미 찾은 친화쌍들 중에 없는 수에 대해서만 확인하면 된다.

또 한가지 이 문제에서 실수하기 쉬운 것은 자기 자신을 제외한 약수의 합이 자신과 같은 수이다. 대표적으로는 1이 그러한데, 이런 수들이 제법 있기 때문에 오답을 내는 경우가 많다. 자기 자신과는 친화쌍을 이루지 않는다.

%%time

def s(n: int) -> int:
  s, l = 1, int(n ** .5)
  a = 2
  while a <= l:
    if n % a == 0:
      s += (a + n // a)
    a += 1
  if l * l == n:
    s -= l
  return s

res = set()
for n in range(2, 10001):
  if n not in res:
    m = s(n)
    if m <= 10000 and m != n and s(m) == n:
      res |= {m, n}
print(sum(res))