# Project Euler 50 Solution: Consecutive prime sum

Problem 50

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

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 = notPrime = 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.

« Back to problem overview