Saturday, June 26, 2010

Find Prime Numbers Using the Sieve of Eratosthenes

Today I want to show you how to implement the Sieve of Eratosthenes in C#, which outputs all primes starting from 2 to an upper border.
As the name of the algorithm stems from the Greek mathematician Eratosthenes of Cyrene, it is called "Sieve of Eratosthenes".
Let N be the upper bound, then the algorithm can be described as follows:
All numbers from 2 to N are written down. The smallest not crossed out number at all times is a prime number. At start this is the 2.
From then on, all multiples of this number are crossed out, it suffices to start with the square of the number.
Now here the code of a C# - console application doing exactly that:

    class SiebDesEratosthenes
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Geben Sie die obere Grenze ein:");
            int UpperBound = int.Parse(Console.ReadLine()); // input upper bound
            bool[] Tagged = new bool[UpperBound + 1]; // array describing which numbers are crossed out

            // initialise arrays
            for (int i = 0; i < Tagged.Length; i++)
                Tagged[i] = false;

            // iterate over all numbers up to the square root of the upper bound
            for (int i = 2; i < Math.Ceiling(Math.Sqrt(UpperBound)); i++)
            {
                if (!Tagged[i])
                {
                    int j = i;
                    // cross out all multiples 
                    while (j * i <= UpperBound)
                    {
                        Tagged[j * i] = true;
                        j++;
                    }
                }
            }

            // alle nicht durchgestrichenen Zahlen ausgeben
            for (int i = 2; i < Tagged.Length; i++)
            {
                if (!Tagged[i])
                    Console.Write(i.ToString() + " ");
            }
        }
    }

No comments:

Post a Comment