The Sieve of Eratosthenes

As an excuse to play with VS 2005 Beta2 bits we just posted, I thought I’d implement the Sieve of Eratosthenes. This is a very cool (and very old) algorithm to find prime numbers.

The basic idea is that you have an array from 0..n, where n is the maximum number to consider for being prime. Then you start at the top of the array and mark off 2 as being prime, then mark off all the multiples of two as being composite. Then start back at zero and find the next unmarked number (in this case 3), it must be prime it is not a multiple of any number below it, as such market it as prime. Then mark all of its multiples as being composite. Repeat until there are no more unmarked items.

I also posted a complete implementation in VB and C#.

Here is the code I ended up with:

       public TimeSpan ComputePrimes()

        {

            Stopwatch sw = new Stopwatch();

            values[0] = Numbers.Prime; //not really... but, it helps

            values[1] = Numbers.Prime;

            sw.Start();

            //Loop through each unset value

            for (int outer = 2; outer != -1; outer = FirstUnset(outer))

            {

                //The next unset value must be prime

                values[outer] = Numbers.Prime;

                //mark out all multiples of this prime as being Composite

                for (int inner = outer*2; inner < values.Length; inner += outer)

                {

                    values[inner] = Numbers.Composite;

                }

            }

            sw.Stop();

            return sw.Elapsed;

        }

        int FirstUnset(int last)

        {

            for (int i = last; i < values.Length; i++)

            {

                if (values[i] == Numbers.Unset) return i;

            }

            return -1;

        }