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)
The Python file is available for download here.