<

[Webinar] Streamline your web hosting managementRegister Today

x

Enumerating Prime Numbers in Excel / VBA

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

[Webinar] Kill tickets & tabs using PowerShell

Are you tired of cycling through the same browser tabs everyday to close the same repetitive tickets? In this webinar JumpCloud will show how you can leverage RESTful APIs to build your own PowerShell modules to kill tickets & tabs using the PowerShell command Invoke-RestMethod.

Join & Write a Comment

Do you use a spreadsheet like Microsoft's Excel?  Have you ever wanted to link out to a non excel file on your computer or network drive?  This is the way I found to do it!
This article covers the basics of data encryption, what it is, how it works, and why it's important. If you've ever wondered what goes on when you "encrypt" data, you can look here to build a good foundation for your personal learning.

Keep in touch with Experts Exchange

Tech news and trends delivered to your inbox every month