Clint Rutkas and I have some friendly back and forth about a couple of things. One is the worth of Visual Basic as a programming language and the other is over who is the better coder. Don’t tell Clint but I have a secret suspicion that he may be the better coder (because he is in his prime and I am past mine) but I will never give up on Visual Basic. In any case we have been talking about a small coding challenge to complicate the discussion. After all facts seldom solve anything but they do add to the discussion. Someone suggested that we both write a program to find the next prime number after 2.2 billion. Sounded like fun to us so we went at it. Now let the discussion begin.
My solution was written in Visual Basic – of course. Clint’s in C# – not a bad choice at all. Clint went for complication and sophistication (there is an option to use threading in his) while I went for simple, basic and old school. My code looks like this:
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
Dim i As Long
Dim timePerParse As Stopwatch
Dim ticksThisTime As Long = 0
timePerParse = Stopwatch.StartNew()
For i = Val(txtStart.Text) To Val(txtEnd.Text) ‘ Could use Step 2 here
If IsPrime(i) Then
ticksThisTime = timePerParse.ElapsedTicks
Dim ts As TimeSpan = timePerParse.Elapsed
lblPrime.Text = i.ToString("###,###,###,###")
lblTime.Text = ts.TotalMilliseconds
Function IsPrime(ByVal n As Long) As Boolean
If (n Mod 2 = 0) Then Return False
If (n < 2) Then Return False
If (n < 4) Then Return True
Dim iMax As Long = Math.Sqrt(n) + 1
Dim i As Integer
For i = 3 To iMax Step 2
If (n Mod i = 0) Then Return False
The primary optimization is the line that uses the square root of n plus 1 to set the bounds of the loop that brut forces through finding if the number is divisible by something. I use the StopWatch object (I blogged about that some time ago) for the timing. I also display the results outside the timed area because I/O takes too much time and isn’t really part of the problem anyway. I played with using Step 2 to pass half as many numbers through the IsPrime function but that didn’t seem to make a whole lot of difference in the time. I was surprised by that and want to look into that some more. It may be that the first compare in the IsPrime function may be faster than I expected or perhaps the compiler is doing some behind the scenes optimization. I’d have to look at the generated IL (Intermediate Language) code to really know for sure.
So what do you think? Is Clint’s code better? How do you define “better” when comparing code like this?
For those of us that are clueless - what values are going in txtStart.Text and txtEnd.Text?
Sorry. Those are inputs from textboxes. I was starting my test with 2,200,000,000 and ending with 3,000,000,000.
We used the same method, brute force. I just made mine so I could abuse my processor a bit more. Excellent solution Alfred.
Note that there is some interesting discussion going on at Clint's blog post so stop by there if you haven't already (or not recently) http://www.betterthaneveryone.com/archive/2009/05/06/861.aspx