Problem 50 : Consecutive prime sum

Problem Statement

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?

Solution

def sieve(n):
    is_prime = [True]*n
    is_prime[0] = False
    is_prime[1] = False
    is_prime[2] = True
    for i in range(3,int(n**0.5+1),2):
        index = i*2
        while index < n:
            is_prime[index] = False
            index = index+i
    prime = [2]
    for i in range(3,n,2):
        if is_prime[i]:
            prime.append(i)
    return prime

prime=sieve(10**6)
val=0
lastj=len(prime)
l=0
for i in range(len(prime)):
    for j in range(i+l, lastj):
        sol = sum(prime[i:j])
        if sol < 1000000:
            if sol in prime:
                l = j-i
                val = sol
        else:
            lastj = j+1
            break

print(val)

Output

997651