Sieve of Eratosthenes

• The Sieve
• C# Code
• Console output

Prime numbers are notably the most discussed and revered topic in mathematics. And rightly so we can find its application in myriad of fields. So what is a prime number?.Any number that is divisible by 1 and itself is a prime number(2,3,5,7.....).Prime number's appliance is far reaching and its application can be found on number theory,encryption to name a few. Here is the wiki link on Prime Numbers that gives an exhaustive information.

For centuries prime numbers captivated the minds of mathematicians. A Greek mathematician named Euclid asserted that ,there are "infinitely many prime numbers".Over the centuries, many mathetimatcians invented ways to extract prime numbers upto a given number N.The process of extracting all the prime numbers up to a given number n is formally termed as "SIEVING".One of the earliest form of sieving was invented by a mathematician named Eratosthenes.A Polymath from Greece and the  first man to calculate the circumference of earth. Let us look at the simple method advised by Eratosthenes to extract all the primes up to a Number N.

Lets say to extract all primes up to 20 (N)

Write down all the numbers from 2 to 20 (1 is not a prime number so u have to exclude them everywhere)

2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20

First number in the List is  2;strike out every 2nd number in the list after it(all multiples of 2).

2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20

Next on the list after 2 is 3;now cross out every 3rd number on the list(all multiples of 3).

2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20

Next on list is 5;cross out every 5th number.A number could have been crossed out on a previous iteration ,which should not be a problem.As you can see below 10 was striked on the first iteration itself and would also be a candidate for 5.

2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20

Next is 7
2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20.(no changes to the list)

Next is 11.
Now you can stop as 11+11 =22 which is greater than your Max number N (20).So no use in proceeding further and can stop.

Now if we read out all the numbers that are not striked,we get the primes.

2  3  5  7  11  13  17  19

C# Implementation

I am using an array to initialize and strike out the numbers.
A StopWatch class to see how much time the program takes to complete the sieving.
A Parallel class to improve the performance a bit.

The following code can sieve only up to  100 Million numbers(100000000).This is due to the fact that ,the array size is limited by system's virtual memory.I am running a AMD A8 4500 with 4GB RAM and this is the max i can go up to.We can still notch up the higher limit by replacing array with a List<T>.But i am not taking that route right now,may be ill improvise on this in future.

Without further ado,here goes the code.

namespace EratosthenesPrimeSieve
{
class Program
{
static int[] numbers = new int[100000000];
static int maxNumber;

static void Main(string[] args)
{
    Console.WriteLine("Please enter a max number ");
    maxNumber = int.Parse(Console.ReadLine());
    Stopwatch sw = new Stopwatch();

    sw.Start();
    for (int num = 2; num < maxNumber + 1; num++)
        numbers[num - 2] = num;
    sw.Stop();
    Console.WriteLine("Array fill complete. Time elapsed :" +
        (double)sw.ElapsedMilliseconds / 1000);

    sw.Restart();
    for (int idx = 0; idx < maxNumber - 3; idx++)
    {
        int num = numbers[idx];
        if (num != 0)
        {
            while (num + idx < maxNumber)
            {
                numbers[idx + num] = '\0';
                num += numbers[idx];
            }
        }
    }
    sw.Stop();
    Console.WriteLine("Removed all non primes from the array. Time elapsed :" +
                        (double)sw.ElapsedMilliseconds / 1000 + "\n" +
                        "Press enter to display all the primes upto " + maxNumber);

    IEnumerable result = numbers.Where(num => num != 0);
    Console.WriteLine("Primes found :" + result.Count());
    Console.ReadLine();
    Parallel.ForEach(result, p => Console.Write(p + ","));

    Console.ReadLine();

}
}
}