Sieve of Eratosthenes

I was rummaging around in some old directories and found an implementation of the Sieve of Eratosthenes that I’d thought I’d share.  I thought I’d share it because of the simplicity of the algorithm, it represented a very enjoyable programming exercise and one that I now use as a standard kata when learning a new language. The Sieve of Eratosthenes is an algorithm used to identify prime numbers.

In it’s simplest form, the algorithm states:

set Array to array of size Nset Array to all truefor i from 2 to N  for each j where i divides j, j from i + 1 to N    set Array(j) to false

Basically, it trawls an array of “on” bits and “turns off” any index that is cleanly divisible by any number less than the square root of it’s size.

Breaking down the class, the entry point is here.  Simple enough, get a list of primes and print it out.

public static void printPrimesUntil(int n){ List primes = getPrimesUntil(n); printList(primes);}

Next up, we initialise our array, remove the non primes (sieving) and return the result.

private static List getPrimesUntil(int n){ bool[] primes = initialiseArrayOfSize(n); sieveNonPrimes(primes); return listFromPrimesSieve(primes);}

Initialisation is simply setting all of the array indices to 1.  We will switch off any index that isn’t prime further in.

private static bool[] initialiseArrayOfSize(int n){ bool[] primes = new bool[n + 1]; for (int i = 0; i <= n; i++) { primes[i] = true; } return primes;}

Here’s the meat of the algorithm.  For each number less than the square root of the size, we turn off any index that is cleanly divisible by that number. There’s a lot of repetition here, so it isn’t the quickest way of performing this, I’ll put some links for further reading at the end.

private static void sieveNonPrimes(bool[] primes){ for (int i = 2; < Math.Sqrt(primes.Length); i++) { for (int p = i+i; p < primes.Length; p += i) { primes[p] = false; } }}

And we’re done!  Just aggregate the remaining bits into a list…

private static List listFromPrimesSieve(bool[] primes){ List; primeList = new List(); for(int i=1; i<primes.length; i++)="" {="" if(primes[i])="" primelist.add(i);="" }="" return="" primelist;="" <="" pre="">

…and print it out.

private static void printList(List primes){ foreach(int prime in primes) { Console.Write(prime + ", "); } Console.WriteLine();}

Full Source:

Now this isn’t the fastest way to search for primes, there are a number of other algorithms that can be used to arrive at the result quicker.  The Sieve of Sundaram and Sieve of Atkin both offer increased performance.

Ashraff Ali Wahab has done an excellent comparison of benchmarks here.

</primes.length;>