Geeks With Blogs
Bob Palmer's Developer Blog .NET, SQL, and Silverlight Development
For anyone participating in Project Euler, one of the first algorithms you will find yourself needing again and again is a good prime number calculator. 

One of the most efficient algorithms (and one that's very easy to code for) is the Sieve of Eratosthenes.  I would recommend hitting this link for a quick review if you are not already familiar with it, since it does a great job of explaining how this algorithm works.

Since I needed this routine for my own calculations, I've included it here to hopefully help other folks out who are hunting the web for this particular code snippet.  This is the basic code, but it can easily be adapted for functions like finding x number of primes, etc.

        public static List GetPrimeArrayByMax(Int32 maxPrime)
        {
            //The goal of this snippent is to return an array of prime
            //numbers up to the maximum number provided.
            //For this we'll use a sieve method and roll forward.
            
            //the list that will store our numbers
            var ret = new List();

            //This is a byte array - one per number. A '0' means the number is prime,
            //and a '1' indicates that the number is a multiple of a prior prime.
            
            List comp = new List();
            comp.AddRange(new Byte[maxPrime]);
            
            //Define our bounds - from 2 to our maximum potential prime
            Int32 n = maxPrime;
            Int32 lobound = 2;

            //And now the meat of the routine - we fill up the byte array.
            //First - we know that for a given maximum, our potential multipliers
            //will not exceed the square root of our max - so there's no point in
            //looping through.
            Int64 ubound = (Int64)Math.Sqrt(n);

            //And here is the loop
            for (Int32 i = 2; i < ubound; i++)
            {
                //We start by finding our first prime
                //i.e. 2,3,5,7,etc. - we do this by checking our byte array,
                //since by definition our primes will be left as '0' as we
                //fill the array forward.
                if (comp[i] == 0)
                {
                    //Once we find one, we do another loop and for each multiple
                    //of this number, we can flag the corresponding position in the
                    //byte array as 1 (i.e. non-prime).  So if we start with 2, we would
                    //flag 4,6,8,etc. up until our max.  On 3, we would flag 6,9,12,etc.
                    for (Int32 z = (i * 2); z < n; z += i)
                    {
                        comp[z] = 1;
                    }
                }
            }

            //Now that our byte array has only primes (up until our pax) still
            //flagged as zero, we can build our return list.
            for (Int32 q = lobound; q < n; q++)
            {
                //if the byte at the corresponding array location
                //is zero, add this index to our return list
                if (comp[q] == 0)
                {
                    ret.Add(q);
                }
            }
            //and return the index.  Note that this starts at 2, since 1
            //by definition is special and is not included.
            return ret;
        }


Enjoy!
-bob


Posted on Sunday, February 14, 2010 8:59 AM | Back to top


Comments on this post: Calculating prime numbers in C#

No comments posted yet.
Your comment:
 (will show your gravatar)


Copyright © BobPalmer | Powered by: GeeksWithBlogs.net