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?

This took a while to solve partly because I went on vacation and partly because I was being a stubborn bonehead.

I initially tried to solve for all possible starting positions. It worked but I soon discovered it would take days to solve. Wanting to avoid using brute force, I instead went about being a smart ass and used a complicated sifter technique. Needless to say it didn’t work very well.

So, I went back to my original algorithm (which works — see below) dropped the starting position to the first 10 rather than the first 500K. Voila: solved in 12 seconds.

import java.util.*;

public class Euler50

{

public static void main(String[] args)

{

Euler50 e = new Euler50();

System.out.format(“Problem: %s\n”, e.getClass().getName());

System.out.format(“Answer = %s\n”, e.Problem());

}

public String Problem ()

{

ArrayList<Integer> P = new ArrayList<Integer>();

P = makePrimes(1000000);

int maxTerms = 0, maxSum = 0, sum = 0, count = 0;

for (int p: P)

{

for (int i = 0; i < 10 ; i++)

{

count = 0;

sum = 0;

for (int n = i; P.get(n) < p/2; n++)

{

sum += P.get(n);

count++;

if (sum > p)

break;

if (sum == p)

{

if (count > maxTerms)

{

maxTerms = count;

maxSum = sum;

System.out.format(“sum:%d, terms:%d\n”, sum, count);

}

}

}

}

}

return String.valueOf(maxSum);

}

public ArrayList<Integer> makePrimes (int lim)

{

ArrayList<Integer> P = new ArrayList<Integer>();

boolean [] isPrime = new boolean [lim+1];

for (int i = 2; i < lim; i++)

isPrime[i] = true;

for (int p = 2; p*p < lim; p++)

if (isPrime[p] == true)

for (int m = p*p; m < lim; m = m+p)

if (m % p == 0)

isPrime[m] = false;

for (int i = 2; i < lim; i++)

if (isPrime[i])

P.add(i);

return P;

}

}

### Like this:

Like Loading...

*Related*