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("S
heet1") ' 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