Project Euler #50 Consecutive prime sum

Question

I'm having trouble optimising the project euler #50 exercise, it runs for around 30-35 seconds, which is terrible performance.

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?

The catch here is that it's not necessary to start from 2, the sum of consecutive primes which add to 953 are starting from 7.

Here's my code :

    static void Main(string[] args)
    {
        int max = 0;
        int maxCount = 1;
        List<int> primes = new List<int>();
        Stopwatch sw = Stopwatch.StartNew();
        bool[] allNumbers = SetPrimes(1000000);
        for (int i = 0; i < allNumbers.Length; i++)
        {
            if (allNumbers[i])
            {
                primes.Add(i);
            }
        }
        foreach (int prime in primes)
        {
            int startingIndex = 0;
            while (primes[startingIndex] < prime/maxCount)
            {
                int n = prime;
                int j = startingIndex;
                int sum = 0;
                int count = 0;
                while (n > 0)
                {
                    sum += primes[j];
                    n -= primes[j];
                    j++;
                    count++;
                }
                if (sum == prime)
                {
                    if (count > maxCount)
                    {
                        maxCount = count;
                        max = prime;
                    }
                }
                startingIndex++;
            }
        }
        sw.Stop();
        Console.WriteLine(max);
        Console.WriteLine($"Time to calculate : {sw.ElapsedMilliseconds}");
        Console.ReadKey();
    }

    private static bool[] SetPrimes(int max)
    {
        bool[] localPrimes = new bool[max + 1];
        for (int i = 2; i <= max; i++)
        {
            localPrimes[i] = true;
        }
        for (int i = 2; i <= Math.Sqrt(max); i++)
        {
            if (localPrimes[i])
            {
                for (int j = i * i; j <= max; j += i)
                {
                    localPrimes[j] = false;
                }
            }
        }
        return localPrimes;
    }

Answer 1

Even though your prime number generator is not the bottleneck, you should not do this:

for (int i = 2; i <= Math.Sqrt(max); i++)
                     ^^^^^^^^^

Do not calculate the same square root in every loop iteration. Sqrt is an expensive enough operation that you don't want to call unnecessarily. Calculate it only once, store that in a variable and use that in the loop.

I couldn't completely analyze your algorithm, but I ran through the first few steps with the debugger. It looks like you're doing a lot of unnecessary work.
For each prime, you start by looking for a sum of length 1, then length 2, then 3, etc. Even if you have already found a sum of length 100, you always start at 0 again. I'm guessing that's where your bottleneck is.
You want to find the longest anyway, so why not start at the maximum length and shorten it as you go? You can stop as soon as you find one. (there are a lot more possible sums of length 2 than of length 500)

My algorithm works like this:
We have a sum of primes: p(1), p(2), p(3), ... p(n-1), p(n)
See if this sum is a prime also (by doing a binary search on the prime numbers)
If it's not, check the next sum of the same length by substracting p(1) and adding p(n+1). Keep doing this until we find a prime or until the sum becomes greater than 1000000.
Then, shorten the length by 1 by subtracting the last prime, so we get the sum p(1),p(2),p(3)...p(n-1) and check each sum of this length, etc.
(This code is a few years old and might still be a little sloppy)

public int Solve050() {
    const int Limit = 1000000;
    int[] primes = WhateverPrimeGenerator.PrimesUpTo(Limit).ToArray();
    int sum = 0, length = 0;
    //Find the maximum possible length by adding up primes, while sum < Limit
    while (sum < Limit) {
        int newSum = sum + primes[length];
        if (newSum >= Limit) break;
        sum = newSum;
        length++;
    }

    int answer = 0;
    for (; length > 1; length--) {
        answer = FindPrime(primes, Limit, sum, length - 1);
        if (answer > 0) break;
        sum -= primes[length - 1];
    }
    return answer;
}

 //Tries to find a prime of sum-length defined by lastIndex
private static int FindPrime(int[] primes, int maxSum, int sum, int lastIndex)
{
    int result = 0;
    int index = lastIndex + 1;
    for (int firstIndex = 0; lastIndex < primes.Length && sum <= maxSum; firstIndex++, lastIndex++) {
        index = Array.BinarySearch(primes, index, primes.Length - index, sum);
        if (index > 0) result = primes[index]; //Prime found
        if (index < 0) index = ~index;
        sum = sum - primes[firstIndex] + primes[lastIndex + 1];
    }
    return result;
}