<

Enumerating Prime Numbers in Excel / VBA

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

Featured Post

Build an E-Commerce Site with Angular 5

Learn how to build an E-Commerce site with Angular 5, a JavaScript framework used by developers to build web, desktop, and mobile applications.

It is not that simple from VBA to display a compressed help file as it should be. API calls and a few tricks are needed. This demo and full code will show you how.
Do you want to increase the data integrity of your Excel worksheets?  Do you input something repeatedly?  Would it be handy to pick the item from a predetermined (by you) list?  READ ON!

Keep in touch with Experts Exchange

Tech news and trends delivered to your inbox every month