<

Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x

Enumerating Prime Numbers in Excel / VBA

Posted on
3,247 Points
247 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
Comment
Author:Ed Covney
0 Comments

Featured Post

Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Join & Write a Comment

Access developers frequently have requirements to interact with Excel (import from or output to) in their applications.  You might be able to accomplish this with the TransferSpreadsheet and OutputTo methods, but in this series of articles I will di…
If you need to forecast numbers -- typically for finance -- the Windows and Mac versions of Excel 2016 have a basket of tools to get the job done.

Keep in touch with Experts Exchange

Tech news and trends delivered to your inbox every month