article

Finding Prime Numbers Tutorial [Finally!]

Email
Submitted on: 5/16/2020 1:36:19 PM
By: Rde 
Level: Intermediate
User Rating: By 2 Users
Compatibility: VB 5.0, VB 6.0
Views: 1069
author picture
 
     Hi and welcome to this prime numbers tutorial.

This is the last update, really. My apologies, I have recently been researching this subject and thought it would be good to share what I had learned. However, none of my sources had mentioned that the number one is considered not to be prime - for mathematical reasons.

I was working on the false assumption that it was. So sorry for any inconvenience for yet another update.

This is intended for those who don't know much about prime number generation or those who just want a working prime number generator that can produce very large numbers.

Includes zipped module.

This article has accompanying files


 
				
'   ''''''''''''''''''''''''''''''''''''''''''
'            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.

winzip iconDownload article

Note: Due to the size or complexity of this submission, the author has submitted it as a .zip file to shorten your download time. Afterdownloading it, you will need a program like Winzip to decompress it.Virus note:All files are scanned once-a-day by Planet Source Code for viruses, but new viruses come out every day, so no prevention program can catch 100% of them. For your own safety, please:
  1. Re-scan downloaded files using your personal virus checker before using it.
  2. NEVER, EVER run compiled files (.exe's, .ocx's, .dll's etc.)--only run source code.
  3. Scan the source code with Minnow's Project Scanner

If you don't have a virus scanner, you can get one at many places on the net including:McAfee.com


Other 25 submission(s) by this author

 


Report Bad Submission
Use this form to tell us if this entry should be deleted (i.e contains no code, is a virus, etc.).
This submission should be removed because:

Your Vote

What do you think of this article (in the Intermediate category)?
(The article with your highest vote will win this month's coding contest!)
Excellent  Good  Average  Below Average  Poor (See voting log ...)
 

Other User Comments

5/16/2020 3:11:10 PMDave Carter

Excellent work Rohan and thanks also for mentioning the 'VB to HTML syntax hilighter by Gerco Dries'.
Happy coding :)
Dave
(If this comment was disrespectful, please report it.)

 

Add Your Feedback
Your feedback will be posted below and an email sent to the author. Please remember that the author was kind enough to share this with you, so any criticisms must be stated politely, or they will be deleted. (For feedback not related to this particular article, please click here instead.)
 

To post feedback, first please login.