Sunday, January 22, 2012

Prime Numbers in C#

I just spend some time at project Euler http://projecteuler.net/ for some brain gymnastics. What I needed was a quick routine to find prime numbers, so I put the sieve of Eratosthenes algorithm into a class, maybe you find it useful. The goal was to keep it simple but effective. The Class gives you a list of prime numbers as integer. You could change that to ulong if you like, but you might have to think about CLS compliance. Here is the code for the prime class, please refer to the comments for explanation. You might want to change the constant maxNumberOfElements into a parameter.
public class hnPrime
   {
      // Amount of numbers to examine
      private const int maxNumberOfElements = 120;

      // Holds the actual prime numbers. Zero based.
      private List<int> primeList = new List<int>();
      
      // property PrimeNumberList
      public List<int> PrimeNumberList
      {
         get { return primeList; }
      }
      
      //constructor
      public hnPrime()
      {
         Sieve();
      }

      private void Sieve()
      {
         // list to find prime numbers. Zero based. Default setting: false
         BitArray StraightNumberList = new BitArray(maxNumberOfElements);

         // to find multiples of p
         int steps;

         // start with 2, first prime
         int p = 2;

         // go thru all numbers
         while (p < maxNumberOfElements)
         {
            // start number to go thru list is always next prime
            primeList.Add(p);

            // starting at p^2, all smaler multiples of p are marked already
            steps = p * p;

            // skip marking if p^2 (steps) >= maxNumberOfElements. All non primes are marked.
            while (steps < maxNumberOfElements)
            {
               // mark all multiples of p
               StraightNumberList[steps - 1] = true;
               steps += p;
            }

            // look at next p...
            p++;
            // ...find next unmarked number = prime
            while ((StraightNumberList[p - 1]) & (p < maxNumberOfElements)) p++;
         }
      }
   }
Let's wrap this class into a little demonstration. Create a form with two buttons "Prime" and "Close", a textbox for which you want to set a vertical scroll bar to display the prime numbers, and a textbox to display elapsed time. You have probably noticed that the timer displays total milliseconds. To get a better picture about elapsed milliseconds run the prime generation several times.
public partial class winMain : Form
   {
      public winMain()
      {
         InitializeComponent();
      }

      private void btnExit_Click(object sender, EventArgs e)
      {
         this.Close();
      }

      private void btnPrime_Click(object sender, EventArgs e)
      {
         // use build in stopwatch
         Stopwatch stopWatch = new Stopwatch();
         stopWatch.Start();

         //Get prime numbers
         hnPrime PrimeNumbers = new hnPrime();

         stopWatch.Stop();

         // Get the elapsed time as a TimeSpan value.
         TimeSpan ts = stopWatch.Elapsed;

         // Format and display the TimeSpan value.
         string elapsedTime = String.Format("{0:00}:{1:00}:{2:00} - {3}",
             ts.Hours, ts.Minutes, ts.Seconds,
             ts.TotalMilliseconds);
         // display time
         txtTimerOut.Text = elapsedTime;
         // show at once
         txtTimerOut.Refresh();

         //list all found prime numbers
         txtOutput.Text = "";
         foreach (int i in PrimeNumbers.PrimeNumberList)
         {
            txtOutput.AppendText(i.ToString() + Environment.NewLine);
         }
      }
   }
Enjoy.

No comments: