오일러 프로젝트 21

오일러 프로젝트 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

접근

자연수 N의 약수의 합은 소인수분해를 통해서 구하는 방법이 별도로 존재한다. 다만 이 문제에서는  10000 이하의 값에 대해서만 계산하면 되므로, 그냥 N의 제곱근까지의 수들로 나눠서 검사하는 방법이 덜 복잡하면서 빠르다. 따라서 약수의 합을 구하는 알고리듬은 다음과 같이 정리한다.

1. 임의의 자연수 N이 주어진다.
2. 2부터 시작하여 N을 나눠본다. N이 a로 나눠진다면 a * b = N 이므로 나눈 몫까지 약수가 될 것이다.
3. 2의 반복을 N의 제곱근까지 시행한다.
4. N이 완전제곱수인 경우, 제곱근은 약수로 2번 계산되었으므로 한 번 빼준다.

친화수의 쌍만 찾기

어떤 수 A에 대해서 약수의 합을 구했을 때 그 값이 B라면, B의 약수의 합도 구해본다. 그리하여 두 수 A, B가 친화쌍이라면 임의의 집합에 추가한다. 중복을 허용하지 않는 집합을 이용해도 좋고, 리스트에 넣고 검사해도 좋은데, 전자의 방법이 훨씬 부담이 덜할 것이다.
실제로 값을 구하는데 걸리는 시간은 매우 짧은 편이다.

def sum_of_divisors(n: int) -> int:
    s = 1
    i = 2
    l = int(n ** 0.5)
    while i <= l:
        if n % i is 0:
            s += i + n // i
        i += 1
    if l * l == n:
        s -= l
    return s
def find_friend_number(n:int) -> int:
    k = sum_of_divisors(n)
    if k != n and sum_of_divisors(k) == n:
        return k
    return None
result = set()
for i in range(2, 10001):
    j = find_friend_number(i)
    if j is not None:
        result.add(i)
        result.add(j)
%time print(sum(result))
#31626
#Wall time: 0 ns