[Euler Project 077] 소수의 합으로 표현하는 가짓수

스프레드시트로 표현한 배열이랑, 코드에서 구하는 배열이랑 의미가 조금 다르다. 아래 코드에서는 누적값을 구한다. 그래서 계산의 summation 루프를 줄인다. 위 그림은 이해를 좋게 하기 위해 누적으로 표현하지 않았다. 가로축은 합이 되는 수, 세로축은 소수이다. 2, 2 는 2를 2를 최소한 한번 포함하여 2 이하의 소수들의 합으로 표현하는 갯수로 1이다. 10, 5 는 10을 5를 최소한 한번 포함하여 5 이하의 소수들의 합으로 표현하는 갯수이다. 5+5와 5+3+2가 있는데, 최대 소수인 5를 10에서 뺀 나머지인 5에 대해 경우의 수를 summation 하여 구할 수 있다.

아래는 파이썬 코드. 2차원 배열이 위 스프레드시트의 것과 다른 점 주의하라.

---

#!/usr/bin/env python

# http://projecteuler.net/index.php?section=problems&id=77

primes = [ 2 ]
n = 3
while n < 1000:
       for p in primes:
               if p*p > n:
                       primes.append(n)
                       break
               if n%p == 0:
                       break
       n+=1
#print(primes)
n_primes = len(primes)

# P[n][i] is the number of ways to construct n by summing primes under primes[i]
P = []
n = 0
P.append([])
for i in range(n_primes):
       P[n].append(0)

n = 1
P.append([])
for i in range(n_primes):
       P[n].append(0)

n = 2
while 1:
       P.append([])
       cnt = 0
       for i in range(n_primes):
               if n == primes[i]:
                       cnt += 1
               if n - primes[i] > 0:
                       cnt += P[n-primes[i]][i]
               P[n].append(cnt)
       n+=1
       #if n > 11:
       #      break
       if cnt >= 5000:
               print(n)
               break
#for pn in P:
#       print(pn)
print(n-1)