Prime number generation with the Sieve of Eratosthenes

Recently I have been getting back into Project Euler problems. One of the most common things I found I needed in my PE tool bag was a method to generate primes quickly, and to determine primality quickly. During a discussion with Darrell Hawley he told me about the Sieve of Eratosthenes. The method I was taking initially to determine primality was the AKS Primality Test, the algorithm, while efficient, was a bit more in depth than I was looking for, however the Sieve of Eratosthenes was simple and quick and deterministic all important factors.

The Sieve
The sieve itself is rather simple and makes sense when you get right down to it. The sieve is based on eliminating prime factors. So, to find the primes below a number ‘n’ we’ll take the following steps in the algorithm:

1.       To start, create a list of bools of size n+1)
a.       this differs from the Wikipedia definition, it is so we can tell if a number ‘x’ is prime by accessing array[x]
b.      We need to initialize this list to be all true, start by making indices 0 and 1 false (not prime)

2.       Start at the first prime, p = 2, and that is true in the array (for prime)

3.       Repeat the following while  p^2 < n
a.       Set all multiples of p to false (since p divides hem they are not prime)
b.      Find the index of the next true value in the array, set p to this number

4.       The list you are left with is a simple prime number test now as well.
a.       If array[i] == true, i is prime, else composite

Now that we have a list of size n+1 that has been sifted for prime numbers we can determine an number of things:

•   We know all the primes below n
•  We know if n is prime
•  We can quickly determine if x is prime if array[x] is true

On my machine (Intel C2D 2.26Ghz running Win7 32bit) I can calculate all the primes under 1,000,000,00 in only 1m15s and I use this method quite frequently in my Project Euler solutions.

My C# code is available as Eratosthenes.cs