Le crible d'Ératosthène Python & C++

Qu'est-ce que le crible d'Ératosthène ?

Le crible d'Ératosthène est le plus simple des cribles de nombres premiers. C'est un algorithme permettant de trouver tous les nombres premiers dans une limite donnée. Il existe plusieurs cribles de nombres premiers, notamment le crible d'Ératosthène, le crible d'Atkin et le crible de Sundaram.

Le mot "tamis« » fait référence à un ustensile servant à filtrer des substances. Dans le même esprit, l’algorithme du tamis dans Python et d'autres langues font référence à une méthode qui filtre les nombres premiers d'une liste d'entiers.

Cet algorithme filtre les nombres premiers par 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 qui n'a que deux diviseurs : 1 et lui-même. Numbers Les nombres qui ne sont pas premiers sont appelés nombres composés.

Pourquoi utiliser le tamis d'Ératosthène ?

Dans la méthode du crible d'Ératosthène, on sélectionne d'abord un petit nombre premier, puis on élimine tous ses multiples. Le processus s'exécute en boucle sur un intervalle donné, produisant efficacement tous les nombres premiers jusqu'à n sans effectuer de divisions successives pour chaque candidat.

Cela rend le crible plus rapide que la vérification de primalité nombre par nombre. Il est largement utilisé en théorie des nombres, en cryptographie, en hachage et en programmation compétitive, où il est nécessaire de générer rapidement de nombreux nombres premiers.

Par exemple :

Prenons la plage de nombres de 2 à 10.

Après application du crible d'Ératosthène, on obtient 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 allant de 2 à la plage n donnée. 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 du nombre sélectionné.

É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 <=).

À noter: Le raisonnement mathématique est assez simple. L'ensemble des nombres n peut être factorisé comme suit :

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 <= . Par conséquent, en parcourant jusqu'à sera suffisant.

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

Exemple travaillé

Exemple :

Prenons un exemple pour voir comment cela fonctionne.

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

Étape 1) Dans la première étape, nous allons prendre une liste de nombres de 2 à 25 puisque nous avons sélectionné n = 25.

Étape 2) On sélectionne ensuite le plus petit nombre de la liste, x. Initialement, x = 2 car c'est le plus petit nombre premier. Puis on parcourt la liste et on marque 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.

À noter: 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 sont les nombres premiers de 2 à 25.

Pseudo-Code

Le pseudo-code suivant décrit la structure de base du crible d'Ératosthène avant sa traduction en code réel.

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++ Code Exemple

Vous trouverez ci-dessous une liste complète C++ Implémentation du crible d'Ératosthène qui affiche tous les nombres premiers jusqu'à une limite supérieure choisie.

#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

Python Le programme implémente le même algorithme en utilisant une liste booléenne et une boucle while.

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 crible d'Ératosthène parcourt l'ensemble des nombres. Il nécessite donc un espace mémoire de O(n) pour stocker les nombres. La situation se complique lorsqu'on cherche des nombres premiers dans un intervalle très vaste, car il est impossible d'allouer un bloc mémoire aussi important pour une valeur de n aussi grande.

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 et marquez les multiples 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 amélioration substantielle 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é

Comprendre la complexité spatiale et temporelle vous aide à choisir entre le tamis classique et le tamis segmenté pour une taille de problème donnée.

Complexité de l'espace:

L'algorithme simple du crible d'Ératosthène nécessite O(n) d'espace mémoire. Le crible segmenté nécessite O() espace auxiliaire.

Complexité temporelle:

La complexité temporelle d'un algorithme classique de crible d'Ératosthène est O(n*log(log(n))). Le raisonnement derrière cette complexité est exposé ci-dessous.

Pour un nombre n donné, le temps nécessaire pour marquer un nombre composé (c'est-à-dire un nombre non premier) est constant. Ainsi, le nombre d'itérations de la boucle 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 comme log(log(n)) :

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

La complexité temporelle sera donc :

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

= n * journal(log(n))

La complexité temporelle est donc O(n * log(log(n))).

Ensuite, vous en apprendrez davantage sur Le Triangle de Pascal.

FAQ