Prime Number Speed

Question

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<int> Primes = new List<int>();
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;

Answer 1

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<int> Primes = new List<int>();
    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.

Answer 2

For building a list of prime numbers This code is about 25% faster in my tests:

EDIT: Minor point: My research has led me to the conclusion this is based on the Sieve of Sundaram.

public static List<int> ESieve1(int upperLimit)
{

    int sieveBound = (int)(upperLimit - 1) / 2;
    int upperSqrt = ((int)Math.Sqrt(upperLimit) - 1) / 2;
    List<int> numbers = new List<int>((int)(upperLimit / (Math.Log(upperLimit) - 1.08366)));
    bool[] PrimeBits = new bool[sieveBound + 1];
    numbers.Add(2);
    for(int i = 1; i <= upperSqrt; i++)
    {
        if(!PrimeBits[i])
        {
            int inc = 2 * i + 1;
            for(int j = i * 2 * (i + 1); j <= sieveBound; j += inc)
            {
                PrimeBits[j] = true;
            }
            numbers.Add(inc);
        }
    }
    for(int i = upperSqrt + 1; i <= sieveBound; i++)
    {
        if(!PrimeBits[i])
        {
            numbers.Add(2 * i + 1);
        }
    }
    return numbers;
}

This uses offset to the index to find the prime number rather than using the index directly.

Whereas just checking for prime not building a list and optimizing the code comes out very fast:

public static bool[] ESieveA(int upperLimit)
{
    int sieveBound = (int)(upperLimit - 1);
    int upperSqrt = (int)Math.Sqrt(sieveBound);
    bool[] PrimeBits = new bool[sieveBound + 1];            
    PrimeBits[0] = true;
    PrimeBits[1] = true;
    for(int j = 4; j <= sieveBound; j += 2)
    {
        PrimeBits[j] = true;
    }
    for(int i = 3; i <= upperSqrt; i += 2)
    {
        if(!PrimeBits[i])
        {
            int inc = i * 2;
            for(int j = i * i; j <= sieveBound; j += inc)
            {
                PrimeBits[j] = true;
            }
        }
    }
    return PrimeBits;
}

This optimizes by setting multiples of 2 first, then all the rest are odd so the outer loop can skip the even numbers and the inner loop only needs to set the odd multiples.