# Euler 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?

﻿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());
}
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])