<

Enumerating Prime Numbers in Excel / VBA

Posted on
3,448 Points
448 Views
Last Modified:
Experience Level: Intermediate
3:46
Ed Covney
Retired USN in '88. Then IT & s/w dev. Fully retired in 2015. Now practicing math skills, long neglected, and learning VBA (to demo math).
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
Author:Ed Covney
0 Comments
Want to troubleshoot the issue of importing contacts from Excel to Outlook error No Named Ranges?? Resolve this problem and get the error-free solution to resolve the “No Named Ranges” error in a hassle-free way.
The block of six octets of a MAC address represents a lot of challenges when it comes to reading, formatting, parsing, validation, and lookup of vendor information. The functions presented here let you read, generate, format, store, list, and report…

Keep in touch with Experts Exchange

Tech news and trends delivered to your inbox every month