' ''''''''''''''''''''''''''''''''''''''''''
' Finding Prime Numbers
' ''''''''''''''''''''''''''''''''''''''''''
' A prime number is a number that can only
' be evenly divided by one and itself.
' But, we can say it must be divisible by
' two distinct numbers, so only by one and
' another unique number  itself. Therefore,
' based on this definition, 1 is not prime.
' There is a good mathematical reason for
' this distinction which we won't go into
' here. See the end of the page for more.
' Firstly, all prime numbers are odd apart
' from two, because all even numbers can be
' divided by 2 (negative 2 is also a prime).
' This of course means that there is no need
' to test even divisors for zero remainder.
' Instead we can simply test for even (<> 2)
' and return False if so, and then just test
' odd numbers to see if they divide into the
' number N without any remainder.
' It is logical that we only need to test
' odd numbers up to half the candidate N to
' find factors of N.
' However, we can do better...
Function IsPrime(ByVal Num As Long) As Boolean
Dim F As Long, S As Long
Num = Abs(Num)
If Num < 3 Then
IsPrime = (Num = 2)
ElseIf Num Mod 2 <> 0 Then
S = Int(Sqr(Num))
For F = 3 To S Step 2
If Num Mod F = 0 Then Exit Function
Next F
IsPrime = True
End If
End Function
' Note that all negative numbers will
' process correctly using this function.
' ''''''''''''''''''''''''''''''''''''''''''
' Square root of N?
' S = Sqr(N)
' Consider, if a divisor F1 is found before
' the square root of N, then the factor F2
' corresponding to F1 must be greater than S.
' F1 * F2 = N
' For example, the Sqr of 81 is 9 (9 * 9 = 81)
' The number 3 divides evenly into 81 (3 * 27)
' So we have already found 27 (27 * 3) and any
' other divisor of N above S must already have
' been found if factors were found below S.
' So factors greater than S have already been
' found with the corresponding < S factor.
' * This means that no factors can be found
' above S if no factors were found below S.
' ''''''''''''''''''''''''''''''''''''''''''
' However, testing all odd numbers (< S) is
' inefficient, and is very slow when testing
' larger numbers for primality.
' Consider, all smaller numbers (tested to see
' if they divide evenly into N) will eliminate
' the need for testing larger numbers that
' these smaller numbers divide evenly into.
' In other words, if 3 does not divide evenly
' into N, then neither can any larger number
' that 3 divides into.
' So we are talking about prime numbers for
' the test for prime numbers, as only numbers
' that cannot be divided evenly into by smaller
' numbers need be tested to see if they divide
' evenly into N.
' ''''''''''''''''''''''''''''''''''''''''''
' Therefore, we can create a list of divisors
' made up of prime numbers.
' 2,3,5,7,11,13... where 4 is evenly divisible
' by 2 so is skipped, 6 by 2 and 3, 8 by 2 and
' 4, 9 by 3, etc...
Call GenerateList(1 To 31622777)
' ''''''''''''''''''''''''''''''''''''''''''
' Then divide N by each prime number in the
' list and test for zero remainder factors,
' and if none found up to S then N is prime.
' Ideally our primes list goes all the way to
' the square root S of the candidate N.
' If not, we test odd numbers up from our
' largest divisor through to S.
' Basically, this is the same as IsPrime above
' except that it uses initial primes to speed
' up the testing of large Long integers.
' You should call GenerateList before using
' this function.
Function IsPrimeLng(ByVal Num As Long) As Boolean
Dim SqrRtNum As Long, ThisPrime As Long
Dim Idx As Long
If Num < 4 Then
If Num > 1 Then
IsPrimeLng = True
ElseIf Num < 0 Then
IsPrimeLng = IsPrimeLng(Abs(Num))
End If
ElseIf Num Mod 2 <> 0 Then ' Test for even
ThisPrime = 1& ' Default 'odds' walk
SqrRtNum = Int(Sqr(Num))
Idx = 1& ' Skip 2 in list
Do While Idx < lPrimesUb ' If list generated
Idx = Idx + 1&
ThisPrime = laPrimes(Idx)
If ThisPrime > SqrRtNum Then Exit Do
If Num Mod ThisPrime = 0 Then Exit Function
Loop
Do Until ThisPrime > SqrRtNum ' Odds walk to Sqr
ThisPrime = ThisPrime + 2&
If Num Mod ThisPrime = 0 Then Exit Function
Loop
IsPrimeLng = True
End If
End Function
' Note that all negative numbers will
' process correctly using this function.
' ''''''''''''''''''''''''''''''''''''''''''
' So why did we generate prime numbers up
' to 31622777?
' 31622777 just happens to be the next prime
' number greater than the square root of the
' maximum Double (before losing precision):
' 1000000000000000
' The square root of this number is 31622776,
' so the largest prime number in our list is
' 31622777.
' Yes, the Double data type can handle much
' larger numbers, but these larger numbers
' are rounded off:
' 999999999999999 = 999999999999999
' 1000000000000000 = 1E+15 ==
' 1000000000000001 = 1E+15 <>
' 1000000000000020 = 1.00000000000002E+15 ==
' 1000000000000023 = 1.00000000000002E+15 <>
' The lack of absolute precision above the
' value 1000000000000000 means we can no longer
' generate valid prime numbers using the Double
' data type above this number.
' BTW, the greatest prime we can produce using
' the Double data type is 999999999999989
' You should call GenerateList before using
' this function.
Function IsPrimeDbl(ByVal Num As Double) As Boolean
' Note : Num <= 1000000000000000#
' Max Double before losing precision
Dim SqrRtNum As Double, ThisPrime As Double
Dim Div As Double, Idx As Long
If Num < 4# Then
If Num > 1# Then
IsPrimeDbl = True
ElseIf Num < 0# Then
IsPrimeDbl = IsPrimeDbl(Abs(Num))
End If
Else
Div = Num / 2#
If Div <> Int(Div) Then ' Test for even
ThisPrime = 1# ' Default 'odds' walk
SqrRtNum = Int(Sqr(Num))
Idx = 1& ' Skip 2 in list
Do While Idx < lPrimesUb
Idx = Idx + 1&
ThisPrime = laPrimes(Idx)
If ThisPrime > SqrRtNum Then Exit Do
Div = Num / ThisPrime
If Div = Int(Div) Then Exit Function
Loop
Do Until ThisPrime > SqrRtNum
ThisPrime = ThisPrime + 2#
Div = Num / ThisPrime
If Div = Int(Div) Then Exit Function
Loop
IsPrimeDbl = True
End If
End If
End Function
' And again, all negative numbers will
' process correctly using this function.
' ''''''''''''''''''''''''''''''''''''''''''
' However, we do have the Variant data type and
' the CDec function to produce primes up to a
' staggering 10000000000000000000000000000
' You really should call GenerateList before
' using this function! Remember, use CDec(vNum).
Function IsPrimeVar(ByRef vNum) As Boolean
'vNum <= CDec(10000000000000000000000000000)
Dim vSqrRtNum, vThisPrime
Dim vDiv, Idx As Long
If vNum < 4 Then
If vNum > 1 Then
IsPrimeVar = True
ElseIf vNum < 0 Then
IsPrimeVar = IsPrimeVar(Abs(vNum))
End If
Else
vDiv = CDec(vNum / 2)
If vDiv <> Int(vDiv) Then ' Test for even
vThisPrime = CDec(1) ' Default 'odds' walk
vSqrRtNum = CDec(Int(Sqr(vNum)))
Idx = 1&
Do While Idx < lPrimesUb
Idx = Idx + 1&
vThisPrime = CDec(laPrimes(Idx))
If vThisPrime > vSqrRtNum Then Exit Do
vDiv = CDec(vNum / vThisPrime)
If vDiv = Int(vDiv) Then Exit Function
Loop
Do Until vThisPrime > vSqrRtNum
vThisPrime = CDec(vThisPrime + 2)
vDiv = CDec(vNum / vThisPrime)
If vDiv = Int(vDiv) Then Exit Function
Loop
IsPrimeVar = True
End If
End If
End Function
' ''''''''''''''''''''''''''''''''''''''''''
' Fundamental Theorem of Mathematics
' ''''''''''''''''''''''''''''''''''''''''''
' Every positive whole number can be written
' as a unique product of prime numbers.
' Basically, prime numbers are the building
' blocks of all other numbers, and these are
' known as composite numbers.
' The number 1 is neither prime nor composite.
' ''''''''''''''''''''''''''''''''''''''''''
' Prime Numbers Module
' ''''''''''''''''''''''''''''''''''''''''''
' Included with this tutorial is the module
' code in the zip to download. I used a
' brilliant tool found here on PSC to create
' this html document from the module:
VB to HTML syntax hilighter by Gerco Dries
' I hope you have found this tutorial helpful.
' I have attempted to be thorough and clear
' for those who don't know this information,
' so I hope none of you feel offended by my
' stating the obvious like I think I know
' more than you.
