<

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

x

Enumerating Prime Numbers in Excel / VBA

Posted on
3,415 Points
415 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

Exploring SharePoint 2016

Explore SharePoint 2016, the web-based, collaborative platform that integrates with Microsoft Office to provide intranets, secure document management, and collaboration so you can develop your online and offline capabilities.

Join & Write a Comment

I tried to use the SharePoint app to Import a Spreadsheet and import an Excel sheet into a Team site made in SharePoint 2016. But that just resulted in getting an error message 'Unknown Error'...
Charts are easy to insert manually but sometimes we need to automate the chart insertion and most of the people find it difficult to control the chart creation and its properties via VBA  In this article, we will learn about how we can use VBA to in…

Keep in touch with Experts Exchange

Tech news and trends delivered to your inbox every month