Prime numbers have important applications in mathematics and computer programming. I met a mathematician on a return trip from Montreal, Canada on his way to a mathematical society meeting in the “Big Easy”. Having studied mathematics a bit (and realizing I could work for 35 years and never publish a new theorem), I asked him what was hot in mathematics. He said cryptography. Large prime numbers are difficult to calculate for super computers, which makes them great as keys for encrypted transactions. And, just recently someone asked me about calculating primes in a way that made it sound like a computer science course project. So, here we are.
I thought of an algorithm and searched on the Internet for a quick answer. It just so happens that my algorithm is a pretty close approximation of the “Sieve of Eratosthenes”. Eratosthenes was a respected scholar and librarian in Alexandria around 250 BC. (Having to go back so far for the originator suggests to me that we would all be more productive with a lot less television. Newton discovered Calculus because there were no sitcoms.)
A prime number is a number that is divisible by itself and 1 only. The Sieve of Eratosthenes instructs that a prime number can be derived by testing all primes less than or equal to the square root of a number. This works because all integers are a product of primes and no prime number will be divisible by a number greater than its square root without a number lesser than its square root also being a divisor. Thus if, we test all primes less than the square root of a number then we can determine if a number is prime.
If we seed our list of primes with 2, a known prime, then we can calculate all of the primes between 2 and n. The limitation to our algorithm will be the largest number we can store of a certain type. In Visual Basic 6 we can use a Long Integer which will allow us to test all of the primes up to about 2.1 billion. The simple user interface for the sample application can be seen in figure 1. Listing 1 provides the basic solution. The solution is described after the listing.
Figure 1: The user interface for the Sieve of Eratosthenes algorithm.
Listing 1: A Windows application in VB6 that calculates prime numbers up to n using the Sieve of Eratosthenes.
1: Option Explicit 2: Private Primes() As Long 3: Private Function GetMax() As Long 4: On Error GoTo Handler 5: GetMax = CLng(Text1.Text) 6: Exit Function 7: Handler: 8: GetMax = 0 9: Err.Raise -1, "GetMax", "Not a number" 10: End Function 11: 12: 13: Private Function IsPrime(ByVal Number As Long) 14: 15: IsPrime = False 16: Dim I As Long 17: For I = LBound(Primes) To UBound(Primes) 18: DoEvents 19: 20: Call UpdateStatus(Number, Primes(I)) 21: If (Number Mod Primes(I) = 0) Then Exit Function 22: If (Primes(I) >= Sqr(Number)) Then Exit For 23: Next 24: IsPrime = True 25: End Function 26: 27: Private Sub UpdateStatus(ByVal Number As Long, ByVal Prime As Long) 28: If (Check1.Value = 0) Then Exit Sub 29: StatusBar1.SimpleText = "Testing " & Number & _ 30: " is divisible by Prime(" & Prime & ") = " & _ 31: (Number Mod Prime = 0) 32: End Sub 33: 34: Private Sub BuildPrimes(ByVal Max As Long) 35: 36: If (Max < 3) Then Exit Sub 37: Dim I As Long 38: 39: For I = 2 To Max 40: If (IsPrime(I)) Then 41: ReDim Preserve Primes(UBound(Primes) + 1) As Long 42: Primes(UBound(Primes)) = I 43: End If 44: Next 45: 46: End Sub 47: 48: Private Sub Command1_Click() 49: On Error GoTo Handler 50: 51: Initialize 52: Dim Value As Variant 53: BuildPrimes (GetMax()) 54: 55: For Each Value In Primes 56: List1.AddItem (Value) 57: Next 58: 59: Exit Sub 60: Handler: 61: MsgBox Err.Description, vbCritical, Err.Source 62: End Sub 63: 64: Private Sub Initialize() 65: ReDim Primes(0) 66: Primes(0) = 2 67: List1.Clear 68: End Sub 69: 70: Private Sub Form_Load() 71: Initialize 72: End Sub
The sieve is comprised of thirteen lines of code on lines 13 through 25. The rest of the code supports simple user interface interactions. We initialize an array of primes with a single prime, 2, on line 66. The IsPrime test begins by assuming the Number argument is not a prime. We use a single loop, looping through all of the primes less than the square root of Number. (The loop is set up on line 17.) We invoke DoEvents to be kind to the user on line 18; this prevents the GUI from appearing to be frozen. On line 20 we update the StatusBar showing the current test value (see figure 1). On line 21 we divide the Number by the candidate known prime on line 21 and exit if Number is divisible by Primes(I), the test prime. If Number is divisible by any prime than Number is not prime. The second test evaluates the candidate prime against the square root of the Number. If we have reached the square root of the Number without finding a divisor then Number is prime. We branch out of the For Loop and return True.
The Sieve of Eratosthenes works as long as we calculate all primes from 2 to n, which ensures that we have all possible prime divisor candidates to check.
About the Author
Paul Kimmel is a freelance writer for Developer.com and CodeGuru.com. Look for his recent book, Visual Basic .Net Unleashed, at a bookstore near you. Paul Kimmel is available to help design and build your .NET solutions and can be contacted at [email protected].