# Enumerating Prime Numbers in Excel / VBA

Posted on
3,524 Points
524 Views
Published
Experience Level: Intermediate
3:48
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11).
The larger templates are marginally faster (4 - 6%) but at great expense: 100's or 1000's of lines of code.

The macro assigned to my "Find Primes" button is listed below:

Option Explicit

Public i As Long
Public j As Long
Public estr As Double
Public esti As Long              ' used with estr to estimate the size of the primes array
Public iend As Long            ' user input - program will enumerate all prime <= iend
Public sr As Long                 ' square root of iend
Public PrX() As Boolean      ' Templated Possible Primes
Public Primes() As Long      ' # Primes <= iend

Sub DefinePrimes()

With ThisWorkbook.Worksheets("Sheet1")   ' rename the sheet if needed
iend = .Cells(1, 5)
If iend < 40 Then
iend = 40
End If

estr = 1 / (WorksheetFunction.Ln(iend) - 1.15)
esti = Int(estr * iend)
ReDim PrX(iend + 30)           ' we always want to have a little extra space
ReDim Primes(esti)               ' we always want to have a little extra space
sr = Sqr(iend)
.Cells(1, 4) = "Find Primes <= "
.Cells(1, 5) = iend
.Cells(2, 4) = "estr ="
.Cells(2, 5) = estr
.Cells(3, 4) = "esti ="
.Cells(3, 5) = esti
.Cells(4, 4) = "sr ="
.Cells(4, 5) = sr
PrX(2) = True
PrX(3) = True
PrX(5) = True
PrX(7) = True
i = 11
Do While i <= iend       ' 2, 3 and 5 define the sieve template
PrX(i) = True          ' I'll copy the template (7 x 11) 77 times
PrX(i + 2) = True      ' turning potential primes "ON"
PrX(i + 6) = True
PrX(i + 8) = True
PrX(i + 12) = True
PrX(i + 18) = True
PrX(i + 20) = True
PrX(i + 26) = True
i = i + 30             ' 30 = 2 * 3 * 5 - size of template
Loop                    ' this section turned "On" all possible primes

For j = 7 To sr            'sr = floor(sqrt(iend))
If PrX(j) Then           ' Turn off those that aren't prime
i = j * j
Do While i <= iend
PrX(i) = False
i = i + j + j             ' j+j is a cycle or two faster than 2*j
Loop
End If
Next

j = 0                      ' if still on, xfer index to list of primes
For i = 2 To iend
If PrX(i) Then
j = j + 1
If j <= esti And PrX(i) <> 0 Then
Primes(j) = i
End If
End If
Next

For i = 1 To j  'esti
.Cells(i, 1) = Primes(i)
Next
.Cells(5, 4) = "P Min ="
.Cells(5, 5) = 2
.Cells(6, 4) = "P Max ="
.Cells(6, 5) = Primes(j)
.Cells(7, 4) = "# Primes ="
.Cells(7, 5) = i - 1

End With

End Sub

Here is the XLSM file for Enumerating Prime Numbers Video::
(On sheet 5, I just found all 74,498 primes in the range [2..999983] in less than one second.)
https://filedb.experts-exchange.com/incoming/2017/03_w13/1153247/SieveTemplates.xlsm
0