오일러 프로젝트 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)

https://repl.it/@sooop/EulerProject-077