Click here to Skip to main content
15,885,875 members
Articles / Programming Languages / C#

Prime Number Determination Using Wheel Factorization

Rate me:
Please Sign up or sign in to vote.
4.84/5 (17 votes)
2 Feb 2009CPOL4 min read 77.4K   719   28  
Determine if an integer is prime, and use Wheel Factorization to improve the algorithm.
using System;
using System.ComponentModel;
using System.Text;
using System.Windows.Forms;

namespace Rick.Oden.PrimeSuspect
{
   public partial class PrimeSuspectForm : Form
   {
      // PrimeSuspect written by Rickie Oden on 9 November 2008
      // PrimeSuspect will determine if an integer is a prime.

      PrimeDeterminer primeDeterminer;  // A background worker to determine if a number is prime

      // The next 3 fields are used to store the previous state of the txtAnInt textbox control.
      private string prevText;
      private int prevSelectionLength;
      private int prevSelectionStart;

      // Constant fields:
      const char PASTECOMMAND = (char)22; // The ASCII value of the paste command character.
      const char BACKSPACE = (char)8;     // The ASCII value of the back space character.
      const char COPYCOMMAND = (char)3;   // The ASCII value of the copy command character.
      const string CAPTION = "Prime Suspect";

      public PrimeSuspectForm()
      {
         InitializeComponent();

         // Save the properties of the text box.
         // Will revert to these values if invalid data is entered.
         prevText = anIntegerTextBox.Text;
         prevSelectionLength = anIntegerTextBox.SelectionLength;
         prevSelectionStart = anIntegerTextBox.SelectionStart;
      }

      private void PrimeSuspectForm_Load(object sender, EventArgs e)
      {
         primeDeterminer = new PrimeDeterminer(1);  // This will initialize the sieve array in PrimeDeterminer
         primeDeterminer.ProgressChanged += pd_ProgressChanged;
         primeDeterminer.RunWorkerCompleted += bw_RunWorkerCompleted;
      }

      private void btnCheck_Click(object sender, EventArgs e)
      {  // Validate then start the background thread to determine if prime
         if (ValidInput())
         {
            ChangeToSearchingMode();
            try
            {
               ulong test = ulong.Parse(anIntegerTextBox.Text);
               primeDeterminer.SetPrimeSuspect(test);
               primeDeterminer.RunWorkerAsync();
            }
            catch
            {  // In case ulong.Parse doesn't work.
               MessageBox.Show("Invalid Input", CAPTION);
               ChangeToReadyMode();
            }
         }
      }

      private bool ValidInput()
      {  // Validate the unsigned long value from the text box
         if (anIntegerTextBox.Text.Length == 0)
         {
            MessageBox.Show("Value cannot be empty.", CAPTION);
            return false;
         }
         try
         {
            decimal d = decimal.Parse(anIntegerTextBox.Text);
            if (d > ulong.MaxValue)
            {
               MessageBox.Show("Integer is too large. It cannot be equal to or greater than 2^64.", CAPTION);
               return false;
            }
            if (d < 1)
            {
               MessageBox.Show("Integer must be greater than zero.", CAPTION);
               return false;
            }
            if (((ulong)d) == 1)
            {
               MessageBox.Show("The integer 1 is not a prime or a composite, it is unity.", CAPTION);
               return false;
            }

         }
         catch (Exception ex)
         {
            MessageBox.Show(ex.Message, CAPTION);
            return false;
         }
         return true;
      }

      public void pd_ProgressChanged(object sender, ProgressChangedEventArgs e)
      {  // Update the progress bar when the background worker reports progress
         progressBar1.Value = e.ProgressPercentage;
      }

      public void bw_RunWorkerCompleted(object sender, RunWorkerCompletedEventArgs e)
      {  // When the background worker finishes it will call this method.
         ChangeToReadyMode();
         if (e.Cancelled)
         {
            MessageBox.Show("Search Cancelled.", CAPTION);
            return;
         }
         if (e.Error != null)
         {
            MessageBox.Show("Search exception: " + e.Error.ToString(), CAPTION);
            return;
         }
         PrimeResult result = (PrimeResult) e.Result;
         if (result.IsError)
         {
            MessageBox.Show("Input Error: " + result.Message, CAPTION);
         }
         else
         {
            MessageBox.Show(result.Message, CAPTION);
         }
      }

      private void anIntegerTextBox_Enter(object sender, EventArgs e)
      {
         // Highlight all the text when the text box becomes the active control
         anIntegerTextBox.SelectAll();
      }

      /// <summary>
      ///  Checks if the input character is a valid integer character
      /// </summary>
      /// <param name="chrIn">The character to be checked for validity.</param>
      /// <returns>Returns true if a valid character is passed in, false otherwise.</returns>
      private bool IsValidChar(char chrIn)
      {
         return char.IsDigit(chrIn);
      }

      /// <summary>
      /// This method is called when the TextBox change event is triggered.
      /// This method will validate all the characters in the TextBox and
      /// revert back to the previous good values if an invalid character is found.
      /// This method is helpful when the user pastes in invalid characters.
      /// </summary>
      /// <param name="sender">Ignored</param>
      /// <param name="e">Ignored</param>
      private void anIntegerTextBox_TextChanged(object sender, EventArgs e)
      {
         bool invalid = false;
         // check if there are any invalid characters.
         for (int i = 0; i != anIntegerTextBox.Text.Length; i++)
         {
            if (!IsValidChar(anIntegerTextBox.Text[i]))
            {
               invalid = true;
               break;
            }
         } // end for

         // Undo the changes if an invalid character was found.
         if (invalid)
         {
            // Revert back to what was in the text box before the change.
            anIntegerTextBox.Text = prevText;
            anIntegerTextBox.SelectionStart = prevSelectionStart;
            anIntegerTextBox.SelectionLength = prevSelectionLength;
         }
      }

      /// <summary>
      /// This method will be called when the TextBox gets a KeyPress event.
      /// This method will validate the key before allowing it to be sent to the TextBox
      /// by calling IsValidChar().
      /// It will also allow the paste command key, backspace key, and copy command key to be entered.
      /// </summary>
      /// <param name="sender">Ignored</param>
      /// <param name="e">Contains the key that was pressed.</param>
      private void anIntegerTextBox_KeyPress(object sender, KeyPressEventArgs e)
      {
         // Save the controls properties before the change. (used in txtAnInt_TextChanged method)
         prevText = anIntegerTextBox.Text;
         prevSelectionLength = anIntegerTextBox.SelectionLength;
         prevSelectionStart = anIntegerTextBox.SelectionStart;

         char c = e.KeyChar;
         if ((c == PASTECOMMAND) || (c == BACKSPACE) || (c == COPYCOMMAND)) // ctrl-v or backspace or ctrl-c was pressed
         {
            return;  // ctrl-v or backspace or ctrl-c is ok, the change event will check the pasted value for validity
         }
         if (!IsValidChar(c))
         {
            e.Handled = true;  // This tells the handler not to do anything with the KeyChar
         }
      }

      private void ChangeToSearchingMode()
      {
         btnCheck.Enabled = false;
         btnEndSearch.Visible = true;
         progressBar1.Visible = true;
      }

      private void ChangeToReadyMode()
      {
         btnCheck.Enabled = true;
         btnEndSearch.Visible = false;
         progressBar1.Visible = false;
      }

      private void btnEndSearch_Click(object sender, EventArgs e)
      {  // Send a cancel message to the background worker.
         primeDeterminer.CancelAsync();
      }

      private void aboutToolStripMenuItem_Click(object sender, EventArgs e)
      {  //Show the about form.
         aboutForm about = new aboutForm();
         about.Show();
      }

      private void testButton_Click(object sender, EventArgs e)
      {  // Run the test code in the specification folder
         bool noErrors = true;
         try
         {
            testButton.Enabled = false;
            Rick.Oden.PrimeSuspect.Specifications.PrimeDeterminerSpec test1;
            test1 = new Rick.Oden.PrimeSuspect.Specifications.PrimeDeterminerSpec();
            test1.PrimeSetup();
            test1.First1000PrimesFound_Synchronously();
            test1.First7000NonPrimesFound_Synchronously();
         }
         catch
         {
            noErrors = false;
            MessageBox.Show("Assert Test Failed!", CAPTION);
         }
         testButton.Enabled = true;
         if (noErrors)
         {
            MessageBox.Show("All Tests Passed.", CAPTION);
         }
      }

   }
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer
United States United States
My name is Rick Oden. I am a software developer living in Colorado. I have been developing code for various companies for more than 19 years. The languages I have used includes Pascal, Visual Basic, Delphi, Plex, C#, and now looking into F#.

Comments and Discussions