Prime Numbers, Code Challenges, and Programming Languages

Computer Science Teacher
Computer Science Teacher - Thoughts and Information from Alfred Thompson

Prime Numbers, Code Challenges, and Programming Languages

  • Comments 4

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
                Exit For
            End If
        Next

        timePerParse.Stop()
        ticksThisTime = timePerParse.ElapsedTicks
        Dim ts As TimeSpan = timePerParse.Elapsed
        lblPrime.Text = i.ToString("###,###,###,###")
        lblTime.Text = ts.TotalMilliseconds


    End Sub
    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
        Next
        Return True
    End Function

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

Page 1 of 1 (4 items)