An integer greater than one is called a prime number if its only positive divisors (factors) are one and itself. For example, the prime divisors of 10 are 2 and 5; and the first six primes are 2, 3, 5, 7, 11 and 13. (ref. http://www.utm.edu/research/primes/largest.html)
Based on this definition, one is able to test a number N for primality simply repetitively testing for divisibility by all numbers up to N-1.
If they all turn out negative, then it is a prime. Notice that 1 is not considered a prime.
The way to test divisibility is the modulo operator, where f is a trial factor. The code snippet that does that would be:
Dim N as Integer ' Note: integers go up to 65535 only
Dim bPrime As Boolean
For N=Lower To Upper ' Lower and Upper are entered by user
bPrime=True ' continue testing as long as true
Dim F as Integer
For F=2 To N-1 ' test all factors from 2 to N-1
If N mod F = 0 then
bPrime= False ' divisible, therefore composite
Exit For ' no more testing required
Endif
Next
If bPrime=true then ' If never got a factor, Prime found
' print N somewhere
End if
Next
The above snippet should work, after suitable arrangements to get values of Lower and Upper, and output results. However, we do not really need to test even numbers above two, since they are all divisible by two. That halves the number of test to be done.
Dim N as Integer ' Note: integers go up to 65535 only
Dim bPrime As Boolean
If Lower <= 2 then
' Output 2 as a prime number
Lower = 3
Elseif Lower mod 2 = 0 then
Lower +=1 ' if Lower is even,start with next odd
End if
For N=Lower To Upper Step 2 ' START FROM AN ODD>=3 AND ONLY ODD
bPrime=True ' continue testing as long as true
Dim F as Integer
For F=3 To N-1 ' FORGET 2 AS A FACTOR FOR ODD NUMBERS
If N mod F = 0 then
bPrime= False ' divisible, therefore composite
Exit For ' no more testing required
Endif
Next
If bPrime=true then ' If never got a factor, Prime found
' print N somewhere
End if
Next
There is also another fact of which we can take advantage. If a number N is composite, at least one of the factors must be equal to or smaller than sqr(N). Take 144=12*12. we cannot have a bigger factor than sqr(N) without creating another one smaller, such as 144=16*9, 24*6, etc. So testing up to sqr(N) is sufficient! We will only change one line in the snippet.
Dim N as Integer ' Note: integers go up to 65535 only
Dim bPrime As Boolean
If Lower <= 2 then
' Output 2 as a prime number
Lower = 3
Elseif Lower mod 2 = 0 then
Lower +=1 ' if Lower is even,start with next odd
End if
For N=Lower To Upper Step 2 ' Test odd numbers above two
bPrime=True ' continue testing as long as true
Dim F as Integer
For F=3 To sqr(N) Step 2' STOP AT SQR(N)
If N mod F = 0 then
bPrime= False ' divisible, therefore composite
Exit For ' no more testing required
Endif
Next
If bPrime=true then ' If never got a factor, got Prime
' print N somewhere
End if
Next
Finally, we do not need to test composites. If N is divisible by F=A*B, then N is divisible by A and N is divisible by B. The process goes on until the factors are prime. Thus we only need to test prime factors. That will reduce the testing by 90%, since primes only occupy about 10% of the (even & odd) number range.
However, there is a price to pay, since we must find the primes to find other primes! Don't worry, we only need primes up to sqr(N), so all we have to do is to STORE primes as we find them, if the Lower limit is 2. If the lower limit is, say, 200, then we still have to find the 46 primes before we can start PRINTING the ones we found. Remember, if we stored all the 46 primes up to 199, we can find all primes up to an upper limit of 199*199=39601! Not a big price to pay, as there are only 54 primes from 2 to 256!
To store the primes, we need to create an array of size 100. Do a calculation of the primes up to 256 (takes the time to blink you eyes), and then start calculating the rest of the primes using this array.
'=============================================================
' ERRATUM: Amir has just pointed out that with integer
' it will work up to 32 bits, about 2,147,483,647.
' I have initially thought (incorrectly) that integer
' defaults to 16 bits. Thanks Amir
' Paul (2003-11-22)
'==============================================================
Dim iMaxP As Integer ' iMaxP = max.size of array iPrime
Dim iPrime(100) As Integer ' iPrime(0)=2, iPrime(1)=3, ...
' calculate to populate the first 54 primes (for UPPER<65535)
' (SEE ERRATUM: sqrt(Integer32.max)=46340, or 4791 primes)
'.....
Dim N as Integer ' Note: I32.max go up to 2147483647
Dim bPrime As Boolean
If Lower <= 2 then
' Output 2 as a prime number
Lower = 3
Elseif Lower mod 2 = 0 then
Lower +=1 ' if Lower is even,start with next odd
End if
For N=Lower To Upper Step 2 ' Test odd numbers above two
bPrime=True ' continue testing as long as true
Dim iSQN As Integer = Math.Sqr(N)
Dim I as Integer
For I=1 To iMaxP '
F=iPrime(I)
If F > iSQN Then
Exit For ' Prime found, Exit
End If
If N mod F = 0 then
bPrime= False ' divisible, therefore composite
Exit For ' no more testing required
Endif
Next
If bPrime=true then ' If never got a factor,= Prime
' print N somewhere
End if
Next
Here it is, basically what you could do to find primes. A few suggestions for improvements:
I have written this in a short time to give an explanation of how one could proceed. If some code does not work, or if you need need more explanation, send me an e-mail and I will be glad to help.
Public Class frmPrimeNumbers
Inherits System.Windows.Forms.Form
=== Windows Form-Designer Generated code inserted here ===
Private Sub frmPrimeNumbers_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
txtLower.Text = ""
txtUpper.Text = ""
txtOutput.Text = ""
btnCalculate.Text = "Calculate Primes"
lblFound.Text = ""
End Sub
Private Sub btnCalculate_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnCalculate.Click
'===============================================
' Finding Prime Numbers
' The idea behind the algorithm is very simple:
' test each odd candidate, N, for divisibility
' by the list of prime factors (P) already found
' if N mod P = 0, then N is composite.
' testing continues with the next candidate.
' if N mod P <> 0 for all P<=SQRT(N), then
' N is prime.
' N is then added to the end of the array of
' prime factors for testing of higher numbers.
' The process is repeated until all ODD numbers
' within the range have been tested.
'===============================================
' For efficiency reasons, we do not test even
' numbers, since all even numebr above TWO are
' composite.
'===============================================
' Note that even if the lower bound is 100,
' it is required to start finding ALL primes
' starting from 3 to have a list of prime fact.
' Those below the lower limit will NOT be
' printed in the Output textbox.
'===============================================
' define an array of prime factor storage
' it will be redimensioned as required later
Dim lngPF() As Long ' storage for prime factors
Dim lngInc As Long = 1000 'memory increment
Dim lngSize As Long = lngInc 'size of array
ReDim lngPF(lngSize) ' start with one inc.
lngPF(0) = 2 ' first prime factor, but not used
' since we skip all even numbers
lngPF(1) = 3 ' first prime factor for tests
Dim lngPFCount As Long = 2 '# of primes stored
Dim lngN As Long ' Prime candidate
Dim lngPtr As Long ' pointer to the PF array
Dim lngF As Long ' current prime fact. tested
Dim lngTotal As Long = 0 'total number of primes
'==============================================
' Clear txtbox
txtOutput.Clear()
' Set Timer to beginning
Dim datStart As Date = DateTime.Now
' Extract and define limits
Dim lngLower As Long = Val(txtLower.Text)
Dim lngUpper As Long = Val(txtUpper.Text)
If lngLower < 2 Then 'lower must be >=2
lngLower = 2
txtLower.Text = lngLower
End If
If lngLower = 2 Then ' output 2 as prime
txtOutput.Text &= "2" + vbNewLine
lngTotal += 1
End If
If lngLower > lngUpper Then 'chk if upper>lower
lngUpper = lngLower
txtUpper.Text = lngUpper
End If
If lngLower <= 3 And lngUpper >= 3 Then
'output 3 if within range, being the
' seed factor
txtOutput.Text &= "3" + vbNewLine
lngTotal += 1
End If
If lngLower Mod 2 = 0 Then
lngLower += 1 'start test with odd number
If lngLower > lngUpper Then
txtOutput.Text = "No prime found between " & txtLower.Text & " and " & txtUpper.Text
Exit Sub
End If
End If
' Calculate the maximum factor to be stored
Dim lngMaxFactor As Long = Math.Sqrt(lngUpper)
'txtOutput.Text &= "MaxFactor=" & Str(lngMaxFactor) & vbNewLine
' Pointer to last factor to test
Dim lngMaxPtr As Long = 1
' maximum prime this factor can test
Dim lngMaxPrime As Long = lngPF(lngMaxPtr) ^ 2
Dim booEnough = False ' =true if enough fact.
' Store original button colour
Dim colBackColour As System.Drawing.Color = btnCalculate.BackColor
' start(heartbeat), change button colour
btnCalculate.BackColor = Color.Coral
btnCalculate.Update()
btnCalculate.Show()
' Now let the show begin
' Even if lngLower>3, we test from three
' so that we have a complete list of prime fact.
'===============================================
' A do-while loop is used here so that we can
' change the parameter when enough factors have
' been collected, but still haven't reached
' the lower limit. For example, if the lower
' limit is 20000, and the upper limit is 30000,
' then prime factors up to sqrt(30000)=173 are
' needed, and the loop variable then jumps from ' 173 to 20001 to start testing for primes.
lngN = 3
Do While lngN <= lngUpper
' if enough factors calculated, skip to
' lower limit requested (must be odd)
If booEnough And lngN < lngLower Then
lngN = lngLower
End If
Dim booPrime As Boolean = True
' Dynamically assign mem. to PF when needed
If lngSize - lngPFCount <= 1 Then
lngSize += lngInc ' need more memory
ReDim Preserve lngPF(lngSize)
End If
' see if the last factor is big enough
If lngMaxPrime < lngN Then
lngMaxPtr += 1
lngMaxPrime = lngPF(lngMaxPtr) ^ 2
End If
For lngPtr = 1 To lngMaxPtr
lngF = lngPF(lngPtr) 'test factor
If lngN Mod lngF = 0 Then 'composite
booPrime = False
Exit For
End If
Next
If booPrime Then ' found prime
' output prime to textbox
If lngN >= lngLower Then
' output only those within range
txtOutput.Text &= lngN & vbNewLine
lngTotal += 1
End If
' add prime to list lngPF if lngMaxFactor Then
booEnough = True
End If
' intentionally overshoots by one
' to care for MaxFactor^2 0 Then
lblFound.Text &= lngHours & " h "
End If
If lngMins > 0 Then
lblFound.Text &= lngMins & " m "
End If
lblFound.Text &= dblSeconds & " s"
End Sub
Private Sub txtLower_TextChanged(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles txtLower.TextChanged
lblFound.Text = ""
txtOutput.Text = ""
End Sub
Private Sub txtUpper_TextChanged(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles txtUpper.TextChanged
lblFound.Text = ""
txtOutput.Text = ""
End Sub
End Class