Visual Basic for Applications/Listing Prime Numbers
Summary
edit.
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 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.
Code Notes
editThe Code Module
editOption 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