Calculating Prime Numbers in Visual Basic 6

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.

Picture missing

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 pkimmel@softconcepts.com.



Comments

  • Why everyone seems to be extremely wrong on the subject off sneakers and as a result why you need to read through this post.

    Posted by BobHotgloff on 05/22/2013 11:35pm

    Standard principles of the shoes that you will really benefit from commencing today. [url=http://www.shoesjp.biz/new-balance【ニューバランス】-c-670.html]ニューバランス[/url] Reasons just about everything you've discovered about sneakers is undoubtedly false and what you ought to be aware of. [url=http://www.shoesjp.biz/nike【ナイキ】-c-634.html]nike[/url] Extra short article content tells you most of the cogs and wheels for sneakers and consequently what one should do right away. [url=http://www.kutujp.biz/]ベルーナ[/url] Innovative shoes Publication Unveils Techniques To Rule The shoes World [url=http://www.kutujp.biz/アディダス-adidas-c-4.html]アディダス シューズ[/url] Howcome almost anything you've heard of sneakers is truly drastically wrong and what you must know. [url=http://www.kutujp.biz/アシックス-asics-c-3.html]アシックス シューズ[/url] The greatest strategy for the sneakers that you could find out about right now. [url=http://www.kutujp.biz/ナイキ-nike-c-13.html]ナイキ スニーカー[/url] Interesting write-up reveal the information around sneakers together with reasons why will need to take action right away. [url=http://www.kutujapan.org/]靴 通販[/url] All new shoes E-book Unveil A Way To Rule The shoes World [url=http://www.kutujapan.org/adidas-アディダス-c-74.html]アディダス シューズ[/url] Hot sneakers E-book Illustrates The Best Ways To Rule The shoes Arena [url=http://www.kutujapan.org/new-balance-ニューバランス-c-13.html]new balance[/url] Whatever the pros aren't going to be declaring on the subject off sneakers plus the way this has effects on you actually. [url=http://www.kutujapan.org/nike-ナイキ-c-78.html]ナイキスニーカー[/url] Why all of them are absolute wrong in regards to shoes and consequently the reason why you need to check this out insider report.

    Reply
  • What..?

    Posted by Mitchell on 02/01/2013 12:13pm

    This can be done in 15 lines using two variables and two loops... Dim i As Integer Dim j As Integer Cls For i = 0 To 100 If i = 2 Then Print 2 End If For j = 2 To i - 1 If i Mod j = 0 Then Exit For ElseIf j = (i - 1) Then Print i End If Next j Next i

    Reply
  • wat the heck

    Posted by Wat on 01/10/2013 01:56pm

    wat the heck this is terrible!

    Reply
  • thema

    Posted by snareenactina on 12/23/2012 06:38pm

    The Chinese central planning capitalists are succeeding in slowing the over heating Chinese economy down towards a growth rate of about 8%, this is prompting the press and aspects of the BlogosFear to conclude that China is heading for a crash, collapse , as illustrated by Marc Faber's continuing commentary - golgotha As a way to break the news that it wasn't going to happen in the manner and with the timing they expected, Jesus pulled them aside and gave them instructions by way of a parable. requestsc businesso optionbutton midpoint enquirerare

    Reply
  • urskoko@yahoo.co.uk

    Posted by k2m on 10/20/2004 02:31pm

    Dear Sir, I would like to know the following small program codes in Visual Basis . These are very easy for you but for me it is really hard and I cant think any more . If you have a little bit free time please show me or guide to me how to solve these programs . Yours truly, Mr. KK MYINT 1. Print the series of prme number depends on the mumber of first prime numbers the user want to see. Eg. If user key in 5, the program need to print 2 3 5 7 11 2. Check the number values that user key in is even or odd. 3.Write a program to print palindrome depends on the users key in number. 4.Writ a program to print the value of factorial. Eg. If user key in 5, the program excute like 5*4*3*2*1 and the result value will be 120. 5. Write a program to change the hours, minutes, seconds format for the number of seconds , which is keyed by user. Eg. If user key in 4552 seconds , the printed result should be like : 1 hour :15 min: 52 sec 6.Write a program to find out the data if user key in the start date and the number of days. Eg if user key in 12/10/04 as start date and 90 days for the number of days. The print output should be 10/01/05 7. writ a program to show the pictures in a folder as slide show by using the drive ,directory and file controls in visual basic. 8. write a program which can calculate the basic operation as the calculator as reading values and addition , multiplication, division , and subtraction. There must be one function , which can clear out the value as C in calculator.

    • iuhyh

      Posted by tkhan420 on 03/07/2005 09:56pm

      jj

      Reply
    Reply
Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • Packaged application development teams frequently operate with limited testing environments due to time and labor constraints. By virtualizing the entire application stack, packaged application development teams can deliver business results faster, at higher quality, and with lower risk.

  • The first phase of API management was about realizing the business value of APIs. This next wave of API management enables the hyper-connected enterprise to drive and scale their businesses as API models become more complex and sophisticated. Today, real world product launches begin with an API program and strategy in mind. This API-first approach to development will only continue to increase, driven by an increasingly interconnected web of devices, organizations, and people. To support this rapid growth, …

Most Popular Programming Stories

More for Developers

RSS Feeds