Problem 050


Project Euler

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?


Another prime problem. Since the prime numbers are consecutive, we can stop when our starting value of the chain of consecutive primes reach half a million. Here is a simple algorithm I used.

start = 2;
sum = start;
i = nextPrimeAbove(start);
count = 1;
maxStart = start
maxCount = count;

while (start < 500000) 
  sum += i;
  ++count;

  if (sum < 1000000)
    if(isPrime(sum) && (maxCount < count))
      maxCount = count;
      maxStart = start;
    i = nextPrimeAbove(i);
  else
    start = nextPrimeAbove(start);
    sum = start;
    i = nextPrimeAbove(start);
    count = 1;

nextPrimeAbove() and isPrime() are self-explanatory. There could be more optimization when sum is greater than a million, we can set start as the nextPrimeAbove(start) and calculate the sum using the maxCount since we really don’t care about any count < maxCount. We can also use more memory to pre-calculate all the cumulative prime sum from 2 to 1000000 and so sum of consecutive prime can be calculate between the differences of two cumulative prime sum. E.g. p=2, sum[2] = 2, p=3, sum[3] = 5,  p=5, sum[5] = 10, and p = 7, sum[7] = 17. Consecutive prime sum from 5 to 17 is sum[17] – sum[3] = 17-5 = 12.

Advertisements