Algorithme du tamis d’Eratosthène : Python, C++ Exemple

Le tamis d’Ératosthène est le tamis à nombres premiers le plus simple. Il s'agit d'un algorithme de nombres premiers permettant de rechercher tous les nombres premiers dans une limite donnée. Il existe plusieurs tamis de nombres premiers. Par exemple, le tamis d'Eratosthène, le tamis d'Atkin, le tamis de Sundaram, etc.

Le mot "tamis« désigne un ustensile qui filtre les substances. Ainsi, l’algorithme de tamisage dans Python et d'autres langages font référence à un algorithme pour filtrer les nombres premiers.

Cet algorithme filtre le nombre premier dans une approche itérative. Le processus de filtrage commence par le plus petit nombre premier. Un nombre premier est un nombre naturel supérieur à 1 et qui n'a que deux diviseurs, à savoir 1 et le nombre lui-même. Les nombres qui ne sont pas premiers sont appelés nombres composés.

Dans le tamis de la méthode Eratosthène, un petit nombre premier est sélectionné en premier et tous ses multiples sont filtrés. Le processus s'exécute en boucle dans une plage donnée.

Par exemple :

Prenons la plage de nombres de 2 à 10.

Après avoir appliqué le Tamis d'Ératosthène, il produira la liste des nombres premiers 2, 3, 5, 7

Tamis algorithmique d'Ératosthène

Voici l’algorithme du Tamis d’Ératosthène :

Étape 1) Créez une liste de nombres de 2 à la plage donnée n. Nous commençons par 2 car c'est le plus petit et le premier nombre premier.

Étape 2) Sélectionnez le plus petit nombre de la liste, x (initialement x est égal à 2), parcourez la liste et filtrez les nombres composés correspondants en marquant tous les multiples des nombres sélectionnés.

Étape 3) Choisissez ensuite le nombre premier suivant ou le plus petit nombre non marqué de la liste et répétez l'étape 2.

Étape 4) Répétez l'étape précédente jusqu'à ce que la valeur de x soit inférieure ou égale à la racine carrée de n (x<=).

Remarque : Le raisonnement mathématique est assez simple. La plage de nombres n peut être factorisée comme-

n=a*b

Encore une fois, n =*

= (facteur inférieur à ) * (facteur supérieur à )

Donc au moins un des facteurs premiers ou les deux doivent être <=. Ainsi, en passant à sera suffisant.

Étape 5) Après ces quatre étapes, les nombres non marqués restants seraient tous les nombres premiers de cette plage n donnée.

Mise en situation :

Prenons un exemple et voyons comment cela fonctionne.

Pour cet exemple, nous retrouverons la liste des nombres premiers de 2 à 25. Donc, n=25.

Étape 1) Dans un premier temps, nous prendrons une liste de nombres de 2 à 25 puisque nous avons sélectionné n=25.

Étape 2) Ensuite, nous sélectionnons le plus petit nombre de la liste, x. Initialement x=2 car c'est le plus petit nombre premier. Ensuite, nous parcourons la liste et marquons les multiples de 2.

Les multiples de 2 pour la valeur donnée de n sont : 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24.

Remarque : La couleur bleue indique le nombre sélectionné et la couleur rose indique les multiples éliminés.

Étape 3) Ensuite, nous choisissons le prochain plus petit nombre non marqué, qui est 3, et répétons la dernière étape en marquant les multiples de 3.

Étape 4) Nous répétons l'étape 3 de la même manière jusqu'à ce que x= ou 5.

Étape 5) Les nombres non marqués restants seraient les nombres premiers de 2 à 25.

Pseudo-code

Begin
	Declare a boolean array of size n and initialize it to true
	For all numbers i : from 2 to sqrt(n)
     		IF bool value of i is true THEN
         			i is prime
         			For all multiples of i (i<n)
             			mark multiples of i as composite
Print all unmarked numbers
End

Tamis d'Ératosthène C/C++ exemple de code

#include <iostream>
#include <cstring>
using namespace std;
void Sieve_Of_Eratosthenes(int n)
{
    // Create and initialize a boolean array
    bool primeNumber[n + 1];
    memset(primeNumber, true, sizeof(primeNumber));
    for (int j = 2; j * j <= n; j++) {
        if (primeNumber[j] == true) {
            // Update all multiples of i as false
            for (int k = j * j; k <= n; k += j)
                primeNumber[k] = false;
        }
    } 
    for (int i = 2; i <= n; i++)
        if (primeNumber[i])
            cout << i << " ";
}
int main()
{
    int n = 25;
    Sieve_Of_Eratosthenes(n);
    return 0;
} 

Sortie :

2 3 5 7 11 13 17 19 23

Tamis d'Ératosthène Python Exemple de programme

def SieveOfEratosthenes(n):
# Create a boolean array
	primeNumber = [True for i in range(n+2)]
	i = 2
	while (i * i <= n):
		if (primeNumber[i] == True):
			# Update all multiples of i as false
			for j in range(i * i, n+1, i):
				primeNumber[j] = False
		i += 1
	for i in range(2, n):
		if primeNumber[i]:
			print(i)
n = 25
SieveOfEratosthenes(n)

Sortie :

2
3
5
7
11
13
17
19
23

Tamis segmenté

Nous avons vu que le tamis d'Ératosthène est nécessaire pour parcourir toute la plage de nombres. Ainsi, il a besoin d’espace mémoire O(n) pour stocker les nombres. La situation se complique lorsque l’on essaie de trouver des nombres premiers dans une vaste gamme. Il n’est pas possible d’allouer un espace mémoire aussi grand pour un n plus grand.

L'algorithme peut être optimisé en introduisant de nouvelles fonctionnalités. L’idée est de diviser la plage de nombres en segments plus petits et de calculer les nombres premiers dans ces segments un par un. Il s’agit d’un moyen efficace de réduire la complexité de l’espace. Cette méthode est appelée un tamis segmenté.

L'optimisation peut être réalisée de la manière suivante :

1. Utilisez un simple tamis pour trouver les nombres premiers de 2 à et stockez-les dans un tableau.
2. Divisez la plage [0…n-1] en plusieurs segments de taille maximum
3. Pour chaque segment, parcourez le segment et marquez le multiple des nombres premiers trouvés à l'étape 1. Cette étape nécessite O() au maximum.

Le tamis régulier nécessite un espace mémoire auxiliaire O(n), tandis que le tamis segmenté nécessite O(), ce qui représente une grande amélioration pour un grand n. La méthode présente également un inconvénient car elle n’améliore pas la complexité temporelle.

Analyse de complexité

Complexité de l'espace:

Le simple tamis de l’algorithme d’ératosthène nécessite un espace mémoire O(n). Et le tamis segmenté nécessite
O() espace auxiliaire.

Complexité temporelle:

La complexité temporelle d'un tamis régulier de l'algorithme d'ératosthène est O(n*log(log(n))). Le raisonnement derrière cette complexité est discuté ci-dessous.

Pour un nombre n donné, le temps nécessaire pour marquer un nombre composé (c'est-à-dire des nombres non premiers) est constant. Ainsi, le nombre de fois où la boucle s'exécute est égal à-

n/2 + n/3 + n/5 + n/7 + ……∞

= n * (1/2 + 1/3 + 1/5 + 1/7 +…….∞)

La progression harmonique de la somme des nombres premiers peut être déduite sous la forme log(log(n)).

(1/2 + 1/3 + 1/5 + 1/7 +…….∞) = log(log(n))

Ainsi, la complexité temporelle sera-

T(n) = n * (1/2 + 1/3 + 1/5 + 1/7 + ……∞)

= n * journal(log(n))

Ainsi la complexité temporelle O(n * log(log(n)))

Ensuite, vous en apprendrez davantage Le Triangle de Pascal

Résumé

• Le tamis d'Ératosthène filtre les nombres premiers dans une limite supérieure donnée.
• Le filtrage d'un nombre premier commence à partir du plus petit nombre premier, « 2 ». Cela se fait de manière itérative.
• L'itération se fait jusqu'à la racine carrée de n, où n est la plage numérique donnée.
• Après ces itérations, les nombres qui restent sont les nombres premiers.