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

# -*- 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이다.