Project Euler Problem 050

# 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

It's a brute-force approach with limits and performance improvements.

The limits are:

• We just evaluate sequences until 500000, all sequences starting with a prime higher than that will be at most of length 1.
• As soon as the subsequence gets higher than 1000000 we stop incrementing that subsequence

The performance improvements are:

• Using a set of primes to check whether the subsequence is a prime or not, checking a set is O(1) and checking a list is O(n).
```from CommonFunctions import find_primes_less_than
from itertools import takewhile

if __name__ == '__main__':
primes = find_primes_less_than(1000000)
prime_set = set(primes)
max_len = 0
result = 0
for i in takewhile(lambda i: primes[i] <= 5000000,
range(len(primes))):
tmp = primes[i]
for j in takewhile(lambda j: tmp + primes[j] <= 1000000,
range(i + 1, len(primes))):
tmp += primes[j]
if j - i + 1 > max_len and tmp in prime_set:
result = tmp
max_len = j - i + 1
print("The result is:", result)
```