 # 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: 1140 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.

 ``` '   '''''''''''''''''''''''''''''''''''''''''' '            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. ``` Download 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:
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 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:

(The article with your highest vote will win this month's coding contest!)
Excellent  Good  Average  Below Average  Poor (See voting log ...) 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.)