45 lines
998 B
Python
45 lines
998 B
Python
from lib_prime import primes
|
|
from functools import lru_cache
|
|
|
|
|
|
def euler_077():
|
|
|
|
def get_prime_sequence_dict(n_max):
|
|
""" Returns a dict that maps a
|
|
current prime to the following prime. """
|
|
ps = primes(n_max)
|
|
ps_current = ps[0]
|
|
ps_dict = {}
|
|
|
|
for p in ps[1:]:
|
|
ps_dict[ps_current] = p
|
|
ps_current = p
|
|
|
|
return ps_dict
|
|
|
|
prime_dict = get_prime_sequence_dict(10000)
|
|
|
|
@lru_cache(maxsize=1000000)
|
|
def possible_sums(n, n_orig, d):
|
|
if d == n_orig:
|
|
return 0
|
|
if n == 0:
|
|
return 1
|
|
if n < 0:
|
|
return 0
|
|
if d > n:
|
|
return 0
|
|
|
|
s_1 = possible_sums(n - d, n_orig, d)
|
|
s_2 = possible_sums(n, n_orig, prime_dict[d])
|
|
return s_1 + s_2
|
|
|
|
for n in range(1000):
|
|
if possible_sums(n, n, 2) > 5000:
|
|
return n
|
|
|
|
|
|
if __name__ == "__main__":
|
|
print("e077.py: " + str(euler_077()))
|
|
assert(euler_077() == 71)
|