오일러 프로젝트 77
77번문제는 앞선 문제인 76번이나 31번과 완전 같은 문제라 할 수 있다. 다만 동전의 액면가가 N 보다 작은 소수들이면 된다.
문제
숫자 10을 소수의 합으로 나타내는 방법은 모두 다섯 가지가 있습니다.
7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2
소수의 합으로 나타내는 방법이 5000가지가 넘는 최초의 숫자는 얼마입니까?
접근
N 값을 2부터 시작해서 1씩 증가하면서 N보다 작은 소수를 구하고, 이 집합을 동전의 집합으로 삼아 N을 만드는 경우의 수를 센다. 이 때 반복적으로 N 보자 작은 소수의 집합을 구하는 작업을 수행하기 때문에, 이 작업을 빠르게 처리하는 것이 전체 퍼포먼스를 향상시키는 길이다.
한계값이 정해진 범위에서 소수의 집합을 가장 빠르게 구할 수 있는 방법은 에라토스테네스의 체를 사용하는 것이고, 오일러 프로젝트를 풀면서 아래의 코드를 유용하게 사용했었다.
def sieve(n):
s = [0, 0] + [1] * (n - 1)
for i in range(2, n):
if s[i] is 1:
s[i*2::i] = [0] * ((n - i) // i)
return [i for i, j in enumerate(s) if j > 0]계산하기
N에 대해서 N보다 작은 소수의 합으로 N을 나타내는 방법은 다음과 같이 계산한다. 이는 31번, 영국 화폐의 조합과 같은 방식으로 풀어낸다.
def calc(n):
ways = [1] + [0] * n
for v in sieve(n):
for i in range(v, n+1):
ways[i] += ways[i - v]
return ways[n]이제 위 함수를 계속호출하면서 값이 5000이상되는 경우를 찾는다.
def e077():
m = 2
while calc(m) <= 5000:
m += 1
print(m)
