"""
   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?
"""

from math import sqrt

def is_prime(n):
    """Returns true if n is a prime number"""
    if n == 2 :
        return True
    if not n % 2 or n < 2:
        return False
    return all(n % x for x in range(3, int(sqrt(n)) + 1, 2))

def get_primes(upper):
    """Generate prime numbers upto upper"""
    yield 2
    p = 3
    while p <= upper:
        if is_prime(p):
            yield p
        p += 2
        
if __name__ == '__main__':
    upper = 1000000
    
    psums = [0]
    for count, prime in enumerate(get_primes(upper)):
        psums.append(psums[count] + prime)
        if psums[count + 1] > upper:
            break

    max_len, max_prime = 1, 2
    for i in range(count + 1):
        for j in range(i + max_len, count + 1):
            if is_prime(psums[j] - psums[i]) and j - i > max_len:
                max_len, max_prime = j - i, psums[j] - psums[i]

    print(max_prime)

"""
NOTE:
We first build a list of the sums of nth primes 
until the sum exceeds our upper bound. While P(k), where k is an
index in the list of the primes , represents P(0) + ... + P(k), 
we can find the sum of P(a) + ... + P(b) by subtracting
the sum P(0) + ... + P(a) from the sum P(0) + ... + P(b).

Then we see if the sum of prime from the ath prime to the bth prime,
where a < b, is a prime number. If it is, and it contains the more terms
than previously found, we update the value of the longest terms and the
prime generated by summing them up.
"""
