Visual Basic for Applications/Listing Prime Numbers
This module implements the Sieve of Eratosthenes method for the listing of prime numbers. It is made to run in Microsoft Excel as a standard VBA module. It lists the prime numbers found between unity and some parameter integer value, on Sheet1 of the Workbook, and makes use of a message box for short listings.
- Overflow is a problem for such procedures, but provided that the input parameter is kept within a few millions or so, overflow is unlikely.
- The method although simple is quite slow, since even to test one single value, the entire sequence of multiples (2,3,5,7,...n) must be completed. Large values of input will take several minutes to complete. A faster approach is to test only those factors that are smaller than the square root of the input value; this modification is used in the procedure GetPrimeFactors().
- Note that the the procedure will clear any contents of Sheet1 before each listing.
- An animated GIF found in Wiki Commons is included in Figure 1 to illustrate the method.
- GetPrimeFactors() and its utility DecMod() list the prime factors of a supplied integer. It is written for the decimal subtype, and so it handles inputs of up to 28 full digits, (assuming all nines). The time to complete varies greatly, depending on how many primes are found. There is one peculiarity noted; for example, with an input of 23 nines the answer takes a very long time, but for 28 nines it takes just fifteen seconds or so. Other values like 20, 21, and 22 nines, and so on, are virtually instantaneous. The use of a string for input in the test procedure testGetPrimeFactors() is simply to prevent Excel from truncating the displayed input integer, and has no bearing on the method used; it is not string math here; just a decimal subtype loop.
The Code ModuleEdit
Option Explicit Sub testListPrimes() 'Run this to list primes in range of 'unity to some integer value Dim nNum As Long 'set upper limit of range here 'eg:1234567 gives 95360 primes from 2 to 1234547 in 3 minutes nNum = 1234567 'MsgBox ListPrimes(nNum) ListPrimes nNum End Sub Function ListPrimes(nInput As Long) As String 'Lists primes in range unity to nInput 'Output to Sheet1 and function name 'Method: Sieve of Eratosthenes Dim arr() As Long, oSht As Worksheet, sOut As String Dim a As Long, b As Long, c As Long, s As Long Dim nRow As Long, nCol As Long 'dimension array ReDim arr(1 To nInput) 'set reference to Sheet1 Set oSht = ThisWorkbook.Worksheets("Sheet1") With oSht .Activate .Cells.ClearContents End With 'fill work array with integers If nInput > 1 Then arr(1) = 0 'exception first element For a = 2 To nInput arr(a) = a Next a Else MsgBox "Needs parameter greater than unity - closing" Exit Function End If 'Sieve of Eratosthenes 'progressively eliminate prime multiples For b = 2 To nInput DoEvents 'yield If arr(b) <> 0 Then 'skip zeroed items 'replace prime multiples with zero s = 2 * b Do Until s > nInput DoEvents 'yield arr(s) = 0 s = s + b Loop End If Next b 'Output of primes sOut = "Primes in range 1 to " & nInput & ":" & vbCrLf nRow = 1: nCol = 1 For c = 2 To nInput If arr(c) <> 0 Then oSht.Cells(nRow, nCol) = c 'primes list to Sheet1 nRow = nRow + 1 If c <> nInput Then 'and accumulate a string sOut = sOut & c & "," Else sOut = sOut & c End If End If Next c ListPrimes = sOut End Function Sub testGetPrimeFactors() 'Run this for prime factors of integer 'Set integer as a string in sIn to avoid display truncation 'Decimal subtype applies and limited to 28 full digits. Dim nIn, sIn As String, Reply, sOut As String, sT As String 'set integer to factorise here, as a string sIn = "9999999999999999999999999999" '28 nines takes 15 seconds nIn = CDec(sIn) sOut = GetPrimeFactors(nIn) MsgBox sOut & vbCrLf & _ "Input digits length : " & Len(sIn) 'optional inputbox allows copy of output Reply = InputBox("Factors of" & nIn, , sOut) End Sub Function DecMod(Dividend As Variant, Divisor As Variant) As Variant ' Declare two double precision variables Dim D1 As Variant, D2 As Variant D1 = CDec(Dividend) D2 = CDec(Divisor) 'return remainder after division DecMod = D1 - (Int(D1 / D2) * D2) End Function Function GetPrimeFactors(ByVal nN As Variant) As String 'Returns prime factors of nN in parameter 'Maximum of 28 digits full digits for decimal subtype input. 'Completion times vary greatly - faster for more primes '20,21,and 22 nines factorise immediately, 23 nines time excessive. '25 nines in 6 seconds. Maximum input takes 15 seconds for 28 nines. Dim nP As Variant, sAcc As String nP = CDec(nP) nP = 2 nN = CDec(nN) sAcc = nN & " = " 'test successive factors Do While nN >= nP * nP DoEvents If DecMod(nN, nP) = 0 Then sAcc = sAcc & nP & " * " nN = nN / nP '(divide by prime) Else nP = nP + 1 End If Loop 'output results GetPrimeFactors = sAcc & CStr(nN) End Function