CodeGuru content and product recommendations are editorially independent. We may make money when you click on links to our partners. Learn More.
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].
