Listing Prime Numbers

Summary

Figure 1:The Sieve of Eratosthenes. It is a methodical procedure for finding prime numbers, originally using a table. Notice that factors are eliminated only up to and including that which exceeds the square root of 120 (= 11). (Graphic by *SKopp* at German Wikipedia

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

The Code Module

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

Contents

Text

Summary

Code Notes

The Code Module

See Also