Project Euler - Problem 50

Horray! Number 50! I've advanced to "level 2" on project euler!

Additionally, it appears I spoke to soon about the easy nature of recent problems! This one was very interesting and took me several attempts to get right. Here's the problem:

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?

My initial approach was to create my prime sieve up to 1000000, then iterate through each prime between 1000 and 1000000, and check for the ability to sum up to that prime number from lower primes. I assumed that in order to maximize the sequence length, the initial prime would be less than 100. Unfortunately this resulted in looping essentially 100,000,000 times, doing a simple summation calculation. The result was that I got the right answer, but it took over a minute to do so! Under project euler rules, the problems are designed to be solved in less than a minute. So back to the drawing board!

The better way was to create an array of prime summations, and then search through the various combinations in that array to find the maximum prime. Since by the time you hit prime # 548, your consecutive sum at that point is breaking 1 million, so that narrows the summation search down to measly ~300,000 iterations - much better!

So first generate my sieve:

var primes = CustomMath.Primes(1000000);

Then I went about creating the prime sum array, which was easy enough:

// create array of prime sums

var prime_sums = new List<int&gt();

prime_sums.Add(0);

prime_sums.Add(2);

int sum = 2;

for (int prime = 2; true; prime++)

{

if (primes[prime])

{

sum += prime;

prime_sums.Add(sum);

}

if (sum > 1000000) break;

}

Next, I searched through the resulting array to find the longest combo resulting in a prime:

int consecCount = 0;

int maxPrime = 0;

// find longest consecutive sequence that is prime

for (int i = 0; i < prime_sums.Count; i++)

{

for (int j = i + consecCount; j < prime_sums.Count; j++)

{

int diff = prime_sums[j] - prime_sums[i];

if (diff < 1000000 && primes[diff])

{

if (j - i > consecCount)

{

consecCount = j - i;

maxPrime = diff;

}

}

}

}

And that does it! The new code gives the correct answer - 997663 - in less than 40ms! What a relief! :)