[Project Euler] Problem 23

원문: Problem 23

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

완전수는 그 수의 진약수들의 합이 그 수와 정확하게 같은 수이다. 예를 들어, 28의 진약수의 합은 1 + 2 + 4 + 7 + 14 = 28이고, 이것은 28이 완전수임을 의미한다.

어떤 수 n의 진약수의 합이 n보다 작다면 그 n을 부족수라고 하며, n을 초과한다면 과잉수라고 한다.

12는 1 + 2 + 3 + 4 + 6 = 16이기에, 가장 작은 과잉수이므로 두 개의 과잉수의 합으로 쓸 수 있는 가장 작은 수는 24이다. 수학적인 분석에 따르면, 28123보다 큰 모든 정수는 두 개의 과잉수의 합으로 쓰여질 수 있음이 보여졌다. 그러나 두 개의 과잉수의 합으로 나타낼 수 있는 가장 큰 수가 이 한계보다 작다는 것을 알고 있을지라도, 이 한계는 분석에 의해서는 더 이상 줄여질 수 없다.

두 개의 과잉수로 쓰여질 수 없는 모든 양의 정수의 합을 구하여라

처음에는 과잉수의 리스트를 구한 다음 1부터 28123 전까지의 모든 수들이 과잉수의 합으로 표현될 수 있는지를 확인했다.

그런데 단순하게 프로그래밍을 해서 돌려본 결과, 대략 3~4분 동안 계산을 했다. 문제는 풀었지만 1~28123의 합에서 두 개의 과잉수 합의 리스트의 합을 빼는 것으로 프로그래밍을 다시 했는데, 10초내로 바뀌었다.

Python

#!/usr/bin/evn python3

import factor # factor는 인수 분해 함수. factor가 리턴하는 값은 {인수: 지수} 사전 객체
              # 다른 글에 있는 factor 코드 참조
def abundant(num):
    divisors = factor.factor(num)
    total = 1
    # 인수의 합 공식 사용
    for key in divisors.keys():
        part_total = 0
        for value in range(divisors[key]+1):
            part_total += key ** value
        total *= part_total
    total -= num # 총 합에서 자기 수를 뺌
    if num < total:
        return True
    else:
        return False

abundant_list = [num for num in range(12, 28123) if abundant.abundant(num)]

sum_abundant = set()
for item1 in abundant_list:
    for item2 in abundant_list:
        if item1 + item2 < 28123:
            sum_abundant.add(item1 + item2)

total = sum(range(1, 28123)) - sum(sum_abundant)

print(total)

접기