I was recently interviewed by a major software company about a contract and asked to provide a code sample implementing the Sieve of Eratosthenes Algorithm. As I was trying to impress my prospective client, I added quite a few whistles and bells to demonstrate my expertise with various aspects of .Net and thought it would be nice to post it here.
The only specs I had were a link to the Wikipedia article and instructions to find the 54321th prime number. The (excellent) Wikipedia article can be found here: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
To find all the prime numbers up to n, the basic algorithm is as follows:
1) Create a list of numbers from 2 to n.
2) Grab the next remaining number in the list, starting with 2.
3) Eliminate all multiples of this number beginning with the square of this number less than or equal to n.
4) Continue steps 2 and 3 until the square of the next remaining number is greater than n.
So for n = 10, we would do the following:
First we create the list:
2, 3, 4, 5, 6, 7, 8, 9, 10
We grab the next number in the list, which is 2.
Starting with the square of this number, we eliminate all multiples less than or equal to n – which would be:
4, 6, 8, 10
Now the list looks like this:
2, 3, 5, 7, 9
Now we take the next remaining number in the list, which is 3.
Starting with the square of 3 = 9, we eliminate all multiples <= 10, which would be 9.
Now the list looks like this:
2, 3, 5, 7, 9
The next available number in the list is 5. The square of 5 is 25, which is bigger than n, so we are done.
A screenshot of the sample program is shown in Figure 1.
Figure 1 – Prime Number Generator
When the user clicks the Start Generator button, the list is cleared and the program begins generating prime numbers up to the number specified by the user. During the generation process, this button will be disabled and the Cancel Generator button will be enabled. A checkbox allows an optional update of the display during processing – with the caveat that this will slow the process down some.
Since we want the GUI to be responsive during the number generation process, we will need to have run the calculations in another thread – otherwise the app would be unresponsive, and unresponsive is not going to impress the person who is thinking of hiring me.
For this application, I created a class called Generator. The Generator class has the following members:
Events:
public event ProcessStatus(string Status) – Sends periodic messages about the current status of processing.
public event ProcessComplete() – Fires when the number generator has completed or been cancelled.
Methods:
public void StartGenerating(int MaxNumber) – Starts the prime number generator.
private void StartGenerating(object sender) – Overloaded method – used internally.
public IEnumerable<int> GetPrimes() - Returns the list of prime numbers. The DataSource of the property will be populated using this function.
public void Cancel() – Stops the prime number generator. The ProcessStatus and ProcessComplete events will be fired.
public void Abort() – Stops the prime number generator, but no events will be fired.
Properties:
public bool Ready – True if the calculation has completed.
public bool Busy – True if calculations are in process.
private bool[] Primes – Boolean array - the index represents the number, and value = true if prime.
Let’s start with the events. In C#, events are declared using delegates. A delegate is just a special variable that represents a function signature. Then the event is declared using the delegate. This is actually best said with code:
public delegate void ProcessStatusEvent(string Status);
public delegate void ProcessCompleteEvent();
public event ProcessStatusEvent ProcessStatus;
public event ProcessCompleteEvent ProcessComplete;
So, the event ProcessStatus is a public event that is of type ProcessStatusEvent, which has been declared as a void function with a single string parameter.
We have to be careful about raising this event in the class because the method call will throw an error if the consumer of the class has not implemented the event. So when this event is raised, we will need to do something like this:
if (ProcessStatus != null)
ProcessStatus("This is a message");
Now let’s look at the meat of the operation – the prime number generator engine. This is a private method that accepts an object parameter. This parameter will actually contain an instance of the Generator class – the one that was instantiated by the GUI. So the GUI will create a Generator class object and implement the public version of the StartGenerating method, passing the max number. This method will then pass itself to the private StartGenerating method via this object parameter.
You may be wondering why the public version of the method is passing itself to the private version of the method – and that aside, why don’t we just declare it as Generator instead of object. The answer to the second question is because we aren’t going to call the private method directly; we are going to run it in another thread. And as it turns out, a method that can be launched as a thread comes in two flavors – no parameter or a single parameter declared as object.
The answer to the other question is this: since this method will be running in another thread, it will be running in another instance and won’t have direct access to the calling thread’s properties and variables. By passing an instance of the calling class to the private method, the private method will be able to interact with the caller – specifically the primes property.
As it turns out, there is also another way to share values between the two instances. We can also declare a variable as static. A static member does not require an instance of the object to be called or used. And further, there will be only one instance of this member regardless of how many instances of the object have been created. So for example, consider the following class:
class Test
{
public static void Bob()
{
MessageBox.Show("Static method call");
}
public void Marley()
{
MessageBox.Show("Non-static method call");
}
}
Here’s how you would call each of these methods:
Test.Bob();
Test t = new Test();
t.Marley();
Note that the first call does not need to create a variable of type Test. This is a static method. A variable or property declared as static can be shared among various instances of the class.
The private StartGenerating method will refer to or update several modular variables that are declared as static:
private static int _maxNumber = 0;
private static bool _isReady = false;
private static bool _isBusy = false;
private static bool _cancel = false;
private static bool _abort = false;
_maxNumber is the upper bound we will be generating primes to. It is the n in the algorithm described above. _isReady and _isBusy are returned by the Busy and Ready properties. The generator will set this to true and false respectively when the calculations have completed. _cancel and _abort are set by the Cancel and Abort methods. The generator will stop if it _cancel becomes true during processing and suppress firing any further events if _abort has been set to true as well.
An ProcessStatus event will be fired each time another iteration is made via a call to a wrapper function named HandleProcessStatus. This method is also defined as static and accepts a Generator object, which in this case will be the same object parameter that was passed and described above. The HandleProcessStatus method thus looks like the following:
private static void HandleProcessStatus(Generator generator,
string status)
{
if (generator.ProcessStatus != null)
generator.ProcessStatus(status);
}
Lastly, I found it convenient to declare some public constants used to provide some standard status messages that this routine will raise back to the GUI:
public const string STATUS_COMPLETE = "Loading...";
public const string STATUS_ERROR = "Error ocurred";
public const string STATUS_CANCEL = "Cancelled";
With all the pieces in place, let’s look at the private StartGenerating method, which will be launched in a separate thread. The comments should help describe what is happening at each step of the process:
/// <summary>
/// StartGenerating
/// </summary>
private void StartGenerating(object sender)
{
//The caller has passed itself
//unbox it as a Generator object
Generator generator = (Generator)sender;
//Initialize the boolean array
generator.Primes = new bool[_maxNumber + 1];
//This will pass status information back to the GUI
//via the ProcessStatus event
string status = null;
try
{
//Load the boolean array with each integer from 2 to _maxNumber
for (long i = 2; i <= _maxNumber; i++)
generator.Primes[i] = true;
//Iterate until all primes have been found
int nextPrime = 1; //Will contain the next item in the list
bool isLastOne = false; //True if this is the last iteration
while (!isLastOne && !_cancel)
{
//Locate next prime
for (nextPrime = nextPrime + 1; nextPrime
<= _maxNumber; nextPrime++)
if (generator.Primes[nextPrime])
break;
//Start with the square of the next prime
int multiple = nextPrime * nextPrime;
//We are done nextPrime^2 is greater than _maxNumber
if (multiple > _maxNumber)
isLastOne = true;
//Eliminate all multiples of nextPrime
while (multiple <= _maxNumber && !_cancel)
{
//Send some feedback to the GUI
HandleProcessStatus(generator,
String.Format("Eliminating: {0}", multiple));
//Flag this item and set the next multiple
generator.Primes[multiple] = false;
multiple += nextPrime;
}
}
//Check for user cancel
if (_cancel)
{
status = STATUS_CANCEL;
_isReady = false;
}
else
{
status = STATUS_COMPLETE;
_isReady = true;
}
}
catch
{
status = STATUS_ERROR;
_isBusy = false;
_isReady = false;
}
finally
{
//abort prevents notifying the GUI
if (!_abort)
{
HandleProcessStatus(generator, status);
_isBusy = false;
if (generator.ProcessComplete != null)
generator.ProcessComplete();
}
}
}
The public version of StartGenerating will accept a maximum value, which will be used to populate _maxNumber, set the various flags appropriatly and launch the the above routine in a separate thread:
public void StartGenerating(int MaxNumber)
{
if (this.Busy)
throw (new System.Exception("Generator is Busy"));
//Initialize
_isBusy = true;
_cancel = false;
_abort = false;
_isReady = false;
_maxNumber = MaxNumber;
//Launch the thread
Thread t = new Thread(StartGenerating);
t.Start((object)this);
}
The only member left to look at of any significance is the GetPrimes() function, which will be hooked up to populate the ListBox’s DataSource property. This function will check the state of calculations and return either the completed list of primes or null if the list is not ready. This function is written as follows:
public IEnumerable<int> GetPrimes()
{
if (_isReady)
{
List<int> result = new List<int>();
for (int i = 0; i <= _maxNumber; i++)
if (Primes[i])
result.Add(i);
return (result);
}
return (null);
}
Using the Generator Class
Now let’s take a look at the GUI. Figure 1 shows how the form should look after adding the appropriate controls – A ListBox, 3 Buttons, Numeric UpdDown, CheckBox and a Label here and there to spice things up. The status display at the bottom is just a Label with the BorderStyle set to Fixed3D. The Anchor properties have been set to each control so that the controls will size correctly as the window is sized.
We begin with the Generator object, which is declared as modular – that is within the class but not inside any function:
private Generator _generator = new Generator();
The form constructor looks like the following:
public frmMain()
{
InitializeComponent();
_generator.ProcessStatus += _generator_ProcessStatus;
_generator.ProcessComplete += _generator_ProcessComplete;
lstOutput.DataSource = null;
lblPrimes.Text = "";
EnableControls();
}
Note the two statements after the InitializeComponent() method call. These hook up the Generator’s ProcessStatus and ProcessComplete methods to two methods cleverly named _generator_ProcessStatus and _generator_ProcessComplete, which will run when the ProcessStatus and ProcessComplete events are fired.
The code for the Start Generator button will make sure that the generator is not busy and will start the process if not. We will be setting the state of this button to Disabled during the processing, so this button should never be clicked while the generator is busy in the first place, but it’s always a good idea to write robust code. Here’s the method that runs when the button is clicked:
private void btnStartGenerator_Click(object sender, EventArgs e)
{
try
{
if (_generator.Busy)
//This shouldn't happen but let's be robust
MessageBox.Show("Prime number generator is busy.");
else
{
//Start the Prime Number Generator
lstOutput.DataSource = null;
lblPrimes.Text = String.Format(
"Primes to {0:#,###,###,###,###,###,###}",
(int)nuMaxNumber.Value);
UpdateStatus(STATUS_WORKING);
_generator.StartGenerating((int)nuMaxNumber.Value);
}
}
catch (System.Exception ex)
{
MessageBox.Show(ex.Message);
}
//Enable/disable the controls
EnableControls();
}
This method sets the ListBox’s DataSource property to null, which will clear any results that may be currently displayed. Next update the display with the display, including a call to UpdateStatus which just populates the Label at the bottom of the form. The reason this was wrapped inside a method will become apparent later. The StartGenerating method is called and the EnableControls method is called, that will disable the Start Generating Button, Max Number NumericUpDown and enable the Cancel button:
private void EnableControls()
{
btnStartGenerator.Enabled = !_generator.Busy;
nuMaxNumber.Enabled = btnStartGenerator.Enabled;
btnCancel.Enabled = !btnStartGenerator.Enabled;
}
The Cancel and Close buttons are trivial and not reproduced here. The first one just invokes the Cancel method and the last one just issues a this.Close() method call to close the form. However we might want to take a look at the FormClosing and FormClosed events.
Since the user can close the form while the generator is calculating, we need to make sure that the program does not continue to run after the main form has been closed. So the FormClosing event will check to see if calculations are in place and if so will call the Abort method and then pause for ½ second. The Abort is basically the same as a Cancel but will suppress the ProcessStatus and ProcessComplete events, which throw an error if the form is closed. Both of these errors will be trapped and ignored if they do happen, but I like writing robust code and I don’t like throwing exceptions if I can avoid it - even if they are handled.
The FormClosed event issues an Application.Exit() method to make sure the app quits:
private void frmMain_FormClosing(object sender, FormClosingEventArgs e)
{
try
{
if (_generator.Busy)
{
_generator.Abort();
System.Threading.Thread.Sleep(500);
}
}
catch
{
}
}
private void frmMain_FormClosed(object sender, FormClosedEventArgs e)
{
try
{
Application.Exit();
}
catch
{
}
}
The ProcessStatus event calls the UpdateStatus method that we saw earlier. The GUI allows the user to suppress status information as the process is running, however we still want to notify the user if the process has completed, been cancelled or resulted in an error. You may recall the public constants defined in the Generator class. Here is where they come in handy. The ProcessStatus method will always display these messages, otherwise follow the users wishes as determined by the state of the checkbox:
private void _generator_ProcessStatus(string Status)
{
if (Status == Generator.STATUS_COMPLETE
|| Status == Generator.STATUS_ERROR
|| Status == Generator.STATUS_CANCEL)
UpdateStatus(Status);
else
if (chkShowStatus.Checked)
UpdateStatus(Status);
}
Now might be a good time to look at why the UpdateStatus method exists as opposed to just setting the Text property of the Label directly. As it turns out – the simple answer is that C# will get upset with you if you do and throw an exception. Actually, the call to this method we first saw in the Start Generator button was not needed. We could have set it directly there, but not in the ProcessStatus event handler. This is because that event is being thrown from another thread running in the background. This is not the same thread that created the Label control and a .Net thread is very jealous about people messing with its GUI and will go crash boom if you try. (Sorry VB 6.0 coders. Don’t kill the messenger.) Figure 2 shows a screenshot of the GUI updating the status during a calculation.
Figure 2 – Updating the status during calculations
Well, as you may have guessed, there is a solution. Remember the delegates we looked at earlier? We will use them again here. What we need to do is declare a delegate with the same signature as UpdateStatus. Hey – we can even give the delegate a descriptive name like UpdateStatusMethod! Ok, so the UpdateStatus method will check to see if the world will end if it just sets the property directly by checking the InvokeRequired property, and if so it will take some evasive action by launching itself via reflection using the Invoke method.
Well – I imagine that for many people, none of this makes any sense – so here’s the deal. If you want the code to blow up, don’t do this. If you don’t want the code to blow up, do this and just accept it!
Here’s how we can safely update the status label whether from the GUI’s thread or a background thread…and it will just sit there and work:
private delegate void UpdateStatusMethod(string Status);
private void UpdateStatus(string Status)
{
try
{
if (this.lblStatus.InvokeRequired)
{
UpdateStatusMethod method
= new UpdateStatusMethod(UpdateStatus);
this.Invoke(method, new object[] { Status});
}
else
{
lblStatus.Text = Status;
Application.DoEvents();
}
}
catch
{
}
}
This is just a simple status display event and I don’t want to bother the user if something became hosed, so the whole thing is wrapped in a try/catch block that ignores any errors.
The ProcessComplete event is even less interesting and just calls a method that will cause the ListBox to be populated:
private void _generator_ProcessComplete()
{
RefreshListBox();
}
RefreshListBox has the same problem and solution that we saw with UpdateStatus. Here’s what this method looks like:
private delegate void RefreshListBoxMethod();
private void RefreshListBox()
{
try
{
if (this.lstOutput.InvokeRequired)
{
RefreshListBoxMethod method
= new RefreshListBoxMethod(RefreshListBox);
this.Invoke(method);
}
else
{
lstOutput.DataSource = _generator.GetPrimes();
lstOutput.Refresh();
EnableControls();
}
}
catch(System.Exception ex)
{
MessageBox.Show(ex.Message);
}
}
The last method we will look at is the SelectedIndexChanged event of the ListBox control. This method will display the nth selected prime number in the ListBox – but only if the list is ready. Just to be cute, I added some code to use a suffix of “st” for item one, “nd” for item 2, “rd” for item 3 and “th” for all other items. Whatever. You can take this stuff too far and I always do! Here’s the last method we will look at:
private void lstOutput_SelectedIndexChanged(object sender, EventArgs e)
{
try
{
if (_generator.Ready)
{
long item = lstOutput.SelectedIndex + 1;
string suffix = null;
switch (item)
{
case 1:
suffix = "st";
break;
case 2:
suffix = "nd";
break;
case 3:
suffix = "rd";
break;
default:
suffix = "th";
break;
}
UpdateStatus(String.Format(
"You have selected the {0} {1} item",
item, suffix));
}
}
catch (System.Exception ex)
{
MessageBox.Show(ex.Message);
}
}
Hope it was helpful! The source code for this project can be downloaded from the link above.