Files
  • main.py
main.py
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
from functools import wraps
import time

def timeit(f):
  @wraps(f)
  def g(*args, **kwds):
    a = time.time()
    r = f(*args, **kwds)
    b = time.time()
    print('{} : {:.4f}'.format(f.__name__, b - a))
    return r
  return g


def sieve(n):
  s = [0, 0] + [1] * (n - 1)
  for i in range(2, n):
    if s[i]:
      s[i*2::i] = [0] * ((n - i) // i)
  return [i for i, j in enumerate(s) if j > 0]

def test(n):
  ws = [1] + [0] * (n)
  for v in sieve(n+1):
    for x in range(v, n+1):
      ws[x] += ws[x - v]
  # print(n, ws)
  return ws[n]

@timeit
def e077():
  m = 2
  while test(m) <= 5000:
    m += 1
  print(m)


e077()

Python 3.6.1 (default, Dec 2015, 13:05:11) [GCC 4.8.2] on linux