VBA Excel - Prime numbers

Ask a question

VBA Excel - Prime numbers


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
If Flag = True Then
If i = 2 Then
est_premier(k) = 1
k = k + 1
est_premier(k) = i
k = k + 1
End If
Flag = True
End If
If k = Rang Then Exit For
Next i
NbPremiers_Eratosthene = est_premier(Rang - 1)
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
Jean-François Pillou

Jean-François Pillou - Founder of CCM
Better known as Jeff, Jean-François Pillou is the founder of CommentCaMarche.net. He is also CEO of CCM Benchmark and digital director at the Figaro Group.

Learn more about the CCM team