VBA Excel - Prime numbers

September 2016


VBA Excel - Prime numbers



Introduction

The Sieve of Eratosthenes is an algorithm allowing us find all the prime numbers up to a specific limit (nth number). This involves looping through all numbers as from 2 to n, to check if the active number is a multiple. If it is not a multiple, then the number is a prime number.

The algorithm

First we will need to list of all the numbers up to NbreMax.
  • 1 is removed.
  • Highlight 2 and eliminate all of its multiple
  • Repeat the operation for the number 3.
  • Choose the smallest non highlighted number and then eliminates all its multiples (number 5,...).
  • Repeat the process until you reach the integer part of the root of n.

All the remaining numbers (up to n) are prime numbers!

The function

This type of function can easily be modified to return an Integer or Long number type ... The code is quite slow to execute, so we will limit ourself to the first 1500 prime numbers ...
Function NbPremiers_Eratosthene(Rang As Long) As Variant
'Check for the nth prime number using the Sieve of Eratosthenes
Dim i As Long, j As Long, k As Long, NbreMax As Long, est_premier(), Flag As Boolean

If Rang >= 1 And Rang <= 1500 Then
ReDim Preserve est_premier(Rang)
k = 0
NbreMax = 20 * Rang 'suffit pour un rang < 1500
Flag = True
For i = 2 To NbreMax
For j = 2 To i
If j = i Then Exit For
If i Mod j = 0 Then Flag = False: Exit For
Next
If Flag = True Then
If i = 2 Then
est_premier(k) = 1
k = k + 1
Else
est_premier(k) = i
k = k + 1
End If
Else
Flag = True
End If
If k = Rang Then Exit For
Next i
NbPremiers_Eratosthene = est_premier(Rang - 1)
Else
NbPremiers_Eratosthene = "Rang trop grand ou trop petit (compris entre 1 et 1500 inclus)."
End If
End Function

Invoking the function

Two methods are available:

The nth prime number

Sub Test()
'To get the 499th prime number :
MsgBox NbPremiers_Eratosthene(499)
End Sub

Get the list of the first 99 prime numbers

Sub ListeNbPrems()
'Get a list of the first 99 prime numbers
Dim i As Long, Msg As String, Tb(98)

For i = 1 To 99
Tb(i - 1) = NbPremiers_Eratosthene(i)
Next i
MsgBox Tb(0) & " " & Tb(1) & " " & Tb(2) & " ... " & Tb(UBound(Tb))
End Sub

Download link

Download the sample workbook here: http://cjoint.com/14au/DHfoihzPEV2.htm

Related :

This document entitled « VBA Excel - Prime numbers » from CCM (ccm.net) is made available under the Creative Commons license. You can copy, modify copies of this page, under the conditions stipulated by the license, as this note appears clearly.