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

• Anonymous
  April 17, 2005
  "List<>.ForEach", excisitely STL-ish.
• Anonymous
  April 17, 2005
  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 outerouter instead of 2outer. 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.
• Anonymous
  April 18, 2005
  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.
• Anonymous
  April 18, 2005
  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
• Anonymous
  April 18, 2005
  The comment has been removed
• Anonymous
  April 21, 2005
  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.
• Anonymous
  April 22, 2005
  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?
• Anonymous
  April 23, 2005
  Yes, I coul dhave used a while loop here, but I just felt more comfortable with the for-loop... either works fine