Project Euler 50 Solution: Consecutive prime sum
The prime 41, can be written as the sum of six consecutive primes:
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
Given a list of prime numbers and a lookup table to check if a certain sum is prime is the key to solve this problem. We can calculate both properties with a simple sieve approach:
const limit = 1000000 const notPrime = new Uint8Array(limit); const primes = []; notPrime[0] = notPrime[1] = 1; for (let i = 2; i < limit; i++) { if (notPrime[i] === 0) { primes.push(i); for (let j = i * i; j < limit; j+= i) { notPrime[j] = 1; } } }
We now can now walk through every prime number and naively sum as far as we can. If we reach the limit of a million, we can break the inner loop early. If we have found a new longest sequence of prime numbers that form a prime itself, we update our statistics, which then looks like this:
let maxSum = 0; let maxRun = -1; for (let i = 0; i < primes.length; i++) { let sum = 0; for (let j = i; j < primes.length; j++) { sum+= primes[j]; if (sum > limit) break; if (!notPrime[sum] && sum > maxSum && j - i > maxRun) { maxRun = j - i; maxSum = sum; } } }
This programm runs in 24ms, where the most time is spend on generating the prime tables and not the actual algorithm.