Project Euler 50 Solution: Consecutive prime sum

Problem 50

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.

« Back to problem overview