The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?



In [1]:

    
from euler import gen_lt, gen_prime



In [2]:

    
def foo(n):
    limit = 10 ** n
    primes = list(gen_lt(gen_prime(), limit))
    ps = set(primes)
    delta_longest = 0
    for i in range(len(primes)):
        total = sum(primes[i:i+delta_longest])
        for j in range(i + delta_longest, len(primes)):
            total += primes[j]
            if total > limit:
                if j - i <= delta_longest:
                    return sum(primes[i_longest:i_longest+delta_longest+1])
                break
            if total in ps and j - i > delta_longest:
                delta_longest = j - i
                i_longest = i
    print i_longest, delta_longest+1, primes[i_longest:i_longest+delta_longest+1], sum(primes[i_longest:i_longest+delta_longest+1])
    # print delta_longest+1
    return sum(primes[i_longest:i_longest+delta_longest+1])



In [3]:

    
n = 2
%timeit foo(n)
foo(n)









    



10000 loops, best of 3: 30.7 us per loop






    Out[3]:





41



In [4]:

    
n = 3
%timeit foo(n)
foo(n)









    



10000 loops, best of 3: 100 us per loop






    Out[4]:





953



In [5]:

    
n = 6
%timeit foo(n)
foo(n)









    



1 loops, best of 3: 41.3 ms per loop






    Out[5]:





997651