bancaldo™

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

What is the first value which can be written as the sum of
primes in over five thousand different ways?

Analisi:

stesso metodo risolutivo visto nei problemi 31 e 76.

python:

import time

START = time.time()

def is_prime(num):
    if num <= 1: return False
    elif num == 2: return True
    elif num % 2 == 0: return False
    else:
        d = 3
        r = int(num**0.5)
        while d <= r:
            if num % d == 0: return False
            d += 2
        return True

PRIMES = [p for p in xrange(2, 500) if is_prime(p)]

def eu_77(limit):
    target = 11
    while True:
        qty = [0] * (target + 1)
        qty[0] = 1
        for p in PRIMES:
            for j in range(p, target + 1):
                qty[j] += qty[j - p]
        if qty[target] > limit:
            return target
        target += 1
 
print "Euler 77: {}".format(eu_77(5000))
print time.time() - START