## Introduction

This is an even faster and more space efficient variation on the implementation for finding prime numbers using Sieve of Eratosthenes.

## Background

We know that all even numbers greater than 2 are not prime, so remove them from the sieve process *a priori*.

## Using the code

Like the Clifford Nelson version, I used a simple array of Boolean for numbers. However, numbers are not represented directly. The boolean at index `n`

represents the number `2n+1`

(for `n > 0`

). So, the array can be half the size of the previous version. My timings show this to be about twice as fast.

Primes up to: |
Previous Version |
This Version |

2,000,000 |
7.7 ms |
3.14 ms |

4,000,000 |
16.41 ms |
7.00 ms |

The attached file has the code with both versions, for calculating the timings.

This code below is just the new implementation. Just copy and paste it into a console app:

class Program
{
private const int repeats = 1000; private const int rawCount = 2000000;
private const int initStart = 1;
private const int count = 1 + (rawCount - 1) / 2; private static readonly int countLimit = (((int)Math.Sqrt(rawCount)) - 1) / 2;
private static bool[] _numbers = new bool[count];
static void Main(string[] args)
{
var sw = new System.Diagnostics.Stopwatch();
for (int j = 0; j < repeats; j++)
{
for (int i = initStart; i < count; i++)
{
_numbers[i] = true;
}
sw.Start();
Run2();
sw.Stop();
}
Console.WriteLine("Milliseconds/run: {0:F2}", sw.ElapsedMilliseconds/(double)repeats);
Console.WriteLine((1 + _numbers.Count(i => i)) + " primes < " + rawCount);
Console.ReadLine();
}
private static void Run2()
{
int baseCounter = 0;
int increment;
int index;
while (baseCounter < countLimit)
{
do
{
baseCounter++;
if (baseCounter == count)
return;
} while (!_numbers[baseCounter]);
increment = (baseCounter << 1) + 1;
index = baseCounter + increment;
while (index < count)
{
_numbers[index] = false;
index += increment;
}
}
}
}

## Points of Interest

I wondered if it would be possible to assume other small prime factors in the sieve and further reduce the array size? I convinced myself that it is **not**, since there are prime pairs that differ by two (such as 11 & 13) so any further compression of the sieve array would not be possible (at least for the Sieve of Eratosthenes).

Strangely, both versions exhibit significant slowdown when the size of the sieve array exceeds about 6MB.

**This improvement of the sieve is not new!** Search Code Project for "Eratosthenes" and you'll find many implementations. Some (probably most) use this type of optimization.

There are other faster methods of finding prime numbers in order, especially for large values, see Sieve of Atkin [^].

## History

9/13/2012 - Initial posting of the Alternative.