Prime summations
Problem 77
It is possible to write ten as the sum of primes in exactly five different ways:
7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2
What is the first value which can be written as the sum of primes in over five thousand different ways?
from tools import rwh_primes2
def run(limit=5000):
max_primeth = 101
primes = list(rwh_primes2(max_primeth))
primes_sum = [0] * max_primeth
primes_sum[0] = 1
for i in range(len(primes)):
for j in range(primes[i], max_primeth):
primes_sum[j] += primes_sum[j - primes[i]]
return min(x for x in range(max_primeth) if primes_sum[x] > limit)