Sunday, May 04, 2008

Sieve of Eratosthenes in C#

I was trying my hands in problems mentioned in Project Euler ( and came across quite a bit questions which had to do with Prime Numbers.

C# doesn't provide any in-built methods to generate prime numbers, but its quite easy to write one. So thought of writing an implementation of the famous "Sieve of Eratosthenes" algorithm to generate prime numbers.

Sieve of Eratosthenes is an easy and straight forward algorithm and can be summarized as follows (courtesy wikipedia)

  1. 1. Write a list of numbers from 2 to the largest number you want to test for primality. Call this List A. (This is the list of squares on the left side of the picture.)
  2. 2. Write the number 2, the first prime number, in another list for primes found. Call this List B. (This is the list on the right side of the picture.)
  3. 3. Strike off 2 and all multiples of 2 from List A.
  4. 4. The first remaining number in the list is a prime number. Write this number into List B.
  5. 5. Strike off this number and all multiples of this number from List A. The crossing-off of multiples can be started at the square of the number, as lower multiples have already been crossed out in previous steps.
  6. 6. Repeat steps 4 and 5 until no more numbers are left in List A. Note that, once you reach a number greater than the Square root of the highest number in List A, all the numbers remaining in List A are prime.

C# Code for the same is as follows.

public static List GeneratePrime(int Range)
var RangeArray = from X in Enumerable.Range(2, Range-1)
where X!=1
select X;

List Results = new List();
var Prime = 2;

while (Prime <= Math.Sqrt(RangeArray.Max()))
Prime = RangeArray.First();
RangeArray = from x in RangeArray where x % Prime != 0 select x;
return Results;

A poem, replicating the essence of the algorithm, is as follows:

Sift the Two's and sift the Three's,
The Sieve of Eratosthenes.
When the multiples sublime,
The numbers that remain are Prime.