프로젝트 오일러(Project Euler) 23번 문제

프로젝트 오일러 23번 문제

---

자신을 제외한 약수(진약수)를 모두 더하면 자기 자신이 되는 수를 완전수라고 합니다. 예를 들어 28은 1 + 2 + 4 + 7 + 14 = 28 이므로 완전수입니다. 또, 진약수의 합이 자신보다 작으면 부족수, 자신보다 클 때는 초과수라고 합니다.

12는 1 + 2 + 3 + 4 + 6 = 16 > 12 로서 초과수 중에서는 가장 작습니다. 따라서 초과수 두 개의 합으로 나타낼 수 있는 수 중 가장 작은 수는 24 (= 12 + 12) 입니다.

해석학적인 방법을 사용하면, 28123을 넘는 모든 정수는 두 초과수의 합으로 표현 가능함을 보일 수가 있습니다. 두 초과수의 합으로 나타낼 수 없는 가장 큰 수는 실제로는 이 한계값보다 작지만, 해석학적인 방법으로는 더 이상 이 한계값을 낮출 수 없다고 합니다.

그렇다면, 초과수 두 개의 합으로 나타낼 수 없는 모든 양의 정수의 합은 얼마입니까?

---

파이썬 코드

# -*- coding: utf-8 -*-
import math
 
#진약수를 모두 더한 값을 반환하는 함수
def divisors_sum(num):
    result = 0
    temp = math.sqrt(num)
       
    #n의 약수를 구할 때, 1부터 루트 n까지만 나눠본다. 나눠서 약수이면, n에서 해당 약수를 나눈 수도 약수이다.
    for i in range(1,int(temp)+1):
        if (num % i == 0):
            result += i + num/i
            if(temp == int(temp) and i == temp): #루트num 중복제거
                result -= i
    
    result -= num #자기자신을 뺀다
    return result
    
 
#num이 초과수이면 true, 아니면 false를 반환하는 함수
def Is_abundant_number(num):
    if(num < divisors_sum(num)): #num의 진약수의 합이 num보다 크면 초과수
        return True                                                                                       
    else:
        return False
        
abundant_list = [] #초과수를 저장할 리스트
sum_abundant_set = set() #2개의 초과수 합을 저장하는 집합
 
for n in range(12,28123):
    if(Is_abundant_number(n) == True): #n이 초과수이면 초과수 리스트(abundant_list)에 저장
            abundant_list.append(n)
    
 
#2개의 모든 초과수 합을 구함
for i in abundant_list:
    for j in abundant_list:
        if(i+j < 28123):
            sum_abundant_set.add(i+j)
        
 
result = sum(range(1,28123)) - sum(sum_abundant_set)
print result

---

풀이

초과수 리스트를 만든다. 초과수 리스트를 이용하여 2개의 초과 수 합 집합을 만든다. 집합을 사용한 이유는 자동으로 중복제거를 하기 위해서이다. 마지막으로 1부터 28123까지 합에서 2개의 초과 수 합을 빼면 답을 구할 수 있다.