반응형
프로젝트 오일러 23번 문제
자신을 제외한 약수(진약수)를 모두 더하면 자기 자신이 되는 수를 완전수라고 합니다. 예를 들어 28은 1 + 2 + 4 + 7 + 14 = 28 이므로 완전수입니다. 또, 진약수의 합이 자신보다 작으면 부족수, 자신보다 클 때는 초과수라고 합니다.
12는 1 + 2 + 3 + 4 + 6 = 16 > 12 로서 초과수 중에서는 가장 작습니다. 따라서 초과수 두 개의 합으로 나타낼 수 있는 수 중 가장 작은 수는 24 (= 12 + 12) 입니다.
해석학적인 방법을 사용하면, 28123을 넘는 모든 정수는 두 초과수의 합으로 표현 가능함을 보일 수가 있습니다. 두 초과수의 합으로 나타낼 수 없는 가장 큰 수는 실제로는 이 한계값보다 작지만, 해석학적인 방법으로는 더 이상 이 한계값을 낮출 수 없다고 합니다.
그렇다면, 초과수 두 개의 합으로 나타낼 수 없는 모든 양의 정수의 합은 얼마입니까?
파이썬 코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | # -*- 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 | cs |
풀이
초과수 리스트를 만든다. 초과수 리스트를 이용하여 2개의 초과 수 합 집합을 만든다. 집합을 사용한 이유는 자동으로 중복제거를 하기 위해서이다. 마지막으로 1부터 28123까지 합에서 2개의 초과 수 합을 빼면 답을 구할 수 있다.
반응형
'programming' 카테고리의 다른 글
| 뇌를 자극하는 C# 5.0 프로그래밍 Chapter8 연습문제 풀이 (0) | 2016.01.08 |
|---|---|
| 뇌를 자극하는 C# 5.0 프로그래밍 Chapter7 연습문제 풀이 (0) | 2016.01.07 |
| 뇌를 자극하는 C# 5.0 프로그래밍 Chapter6 연습문제 풀이 (0) | 2016.01.04 |
| 프로젝트 오일러(Project Euler) 22번 문제 (0) | 2016.01.04 |
| 뇌를 자극하는 C# 5.0 프로그래밍 Chapter5 연습문제 풀이 (0) | 2016.01.04 |
