Python Implementation of Problem 50
View source code here on GitHub!
Includes
Problem Solution
Project Euler Problem 50
Again, surprised how effective the brute force solution was
Revision 1:
Old solution stopped working for some reason. Re-did it starting from the biggest possible space this time
Problem:
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?
1"""
2Project Euler Problem 50
3
4Again, surprised how effective the brute force solution was
5
6Revision 1:
7
8Old solution stopped working for some reason. Re-did it starting from the biggest possible space this time
9
10Problem:
11
12The prime 41, can be written as the sum of six consecutive primes:
1341 = 2 + 3 + 5 + 7 + 11 + 13
14
15This is the longest sum of consecutive primes that adds to a prime below one-hundred.
16
17The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.
18
19Which prime, below one-million, can be written as the sum of the most consecutive primes?
20"""
21from typing import List
22
23from .lib.iters import groupwise
24from .lib.primes import is_prime, primes
25
26
27def main() -> int:
28 iter_primes = iter(primes())
29 cached_primes: List[int] = []
30 while sum(cached_primes) < 1_000_000:
31 cached_primes.append(next(iter_primes))
32 cached_primes.pop()
33 for number in range(len(cached_primes), 21, -1):
34 for group in groupwise(cached_primes, number):
35 total = sum(group)
36 if is_prime(total):
37 return total
38 return -1 # pragma: no cover