Prime Number Speed

I know prime number programs have been beaten to death. I have been programming for eight years (not that long, but I'm not in my 20s yet and I got a programming job straight out of high school so I'm not doing too shabby). Everyone's first instinct is the "Naive" approach (nested loops, check for divisors), and I wrote my fair share of prime number programs. Over the years, those programs have gotten faster and faster, but I now believe I have reached the fastest possible C# implementation of a prime number finder. It uses a prime sieve and has a small memory footprint. I was wondering if there are any optimizations that anybody else can think of?

List Primes = new List();
Primes.Add(2);

int half = count/2 + 1;
bool[] nums = new bool[half];

for (int i = 0;i<half;i++)
{
    if (!nums[i])
    {
        int number = i * 2 + 3;
        Primes.Add(number);
        for (int j = i + number; j < half; j += number)
        {
            nums[j] = true;
        }
    }
}
return Primes;

There is an optimization you can still take advantage of. When you mark your prime multiples, you do not need to mark prime multiples that are less than prime * prime. This is because all smaller multiples are the prime number times some number that is either a smaller prime, or a composite of smaller primes. But earlier loops that processed those primes will have already marked those.

As an example, when number is 5, your code will start the inner loop with j=6 (which represents 15). That will already have been marked when the inner loop ran for the prime number 3. You only need to start at j=11 (which represents 25). Not only will this save you spending time re-marking already marked composites, you will not even need to run the inner loop once your prime number has reached the square root of the limit. However, in testing, the cost of doing the square root made it slightly better to just test against a literal value of the square root of Int32.MaxValue.

Here is your code with three lines modified to take this additional optimization. In my test, it is only a little faster for small limits, but the advantage increases as the limit increases. For large limits it is around 18% faster.

List Primes = new List();
    Primes.Add(2);

    int half = count / 2 + 1;
    bool[] nums = new bool[half];
    var limit = 46340; //(int)Math.Sqrt(int.MaxValue);
    for (int i = 0; i < half; i++) {
        if (!nums[i]) {
            int number = i * 2 + 3;
            Primes.Add(number);
            if (number <= limit) {
                for (int j = ((number * number)/2) -1; j < half; j += number) {
                    nums[j] = true;
                }
            }
        }
    }
    return Primes;

This doesn't fix the small edge problem in your code that sometimes includes primes past the limit. You could make an additional possible optimization by just blasting through the rest of the nums array the first time you exceed limit rather than repeat the (number <= limit) test multiple times.

StackExchange Code Review Q#53840, answer score: 3