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;


        }


 


 


 

Comments (8)

  1. "List<>.ForEach", excisitely STL-ish.

  2. Jeffrey Sax says:

    Congratulations to all teams for shipping beta2! I got it downloaded overnight, but haven’t had a chance to play with it yet.

    Your sieve implementation can be optimized a bit: You can start the inner loop at outer*outer instead of 2*outer. All smaller multiples of outer have already been crossed out.

    Technically, 0 or 1 are neither prime or composite. (See http://en.wikipedia.org/wiki/Prime_number) Values[0] and values[1] aren’t referenced anywhere, so I don’t think it helps to set them.

  3. Erik Sargent says:

    What would be really cool is too use this as an example of how to do distributed/grid computing. There is a lot of excitement around this, but us regular business programmer types are still trying to figure out how to make it useful outside of modeling global warming or nuclear detonations or DNA protiens. Familiarity with the "how" might spark some ideas on what could be useful.

  4. Lee says:

    You’re leaving out one grand optimization. To determine the primes up to n, you need only to "seive" the factors (you call it "outer") up to floor(sqrt(n)).

    MathWorld has a great explanation of of the algorithm here: http://mathworld.wolfram.com/SieveofEratosthenes.html

  5. Lee says:

    Erik: It would be _possible_ to demonstrate grid computing using this problem, but the problem isn’t really well suited for it.

    Grid computing is best used for problems that you can break into many smaller problems — each of which take up an appreciable amount of CPU time. Ideally, the problem solutions shouldn’t really affect eachother. Chess, for example, lends itself well to this type of solution. When you’re looking at the board, you can explore each possibility independently. "What happens if I move my Knight?" "What happens if I move my Queen?" If each of those questions takes your computer 1 hour to answer, you could very well have a 10-hour task on your hands.

    Instead, you might ask one question of each of your ten computers in a cluster. They’ll all compute the answer, and get back to you. Since you did it in parallel, you’ll have the answer in an hour.

    You’ll notice that this problem, though, doesn’t have a nice way of partitioning the problem into computationally intensive pieces. You could definitely parcel out some of the work, but merging the results back into the main "values" array would take more time than generating it in place.

  6. At the end of this article

    http://www.theserverside.net/articles/showarticle.tss?id=IteratorsWithC2

    I show how to use C#2 Iterators to implement the sieve of Erathostene,

    Very useful in the coding day life, isn’t it?

    Actually yes since it helps to pinpoint a limitation of C#2 Iterators.

  7. asqui says:

    Personally I tend to use the <em>for</em> loop for determistic iterations, usually counting the loop variable up (or down) between set boundaries.

    It took me a few seconds to understand what the loop was doing, and I must admit that if you’d given me that code snippet with the for loop taken out and asked me to implement the loop, I would have chosen a <em>while</em> loop:

    <code><tt>int outer = 2;

    while (outer != -1)

    {

    […]

    outer = FirstUnset(outer);

    }

    </tt></code>

    My question is, was there any particular reason you chose to use a <em>for</em> loop, or is it just down to you programming style?

  8. BradA says:

    Yes, I coul dhave used a while loop here, but I just felt more comfortable with the for-loop… either works fine