Crible d'Ératosthène
méthode pour trouver les nombres premiers De Wikipédia, l'encyclopédie libre
Pour les articles homonymes, voir Ératosthène (homonymie).
Le crible d'Ératosthène est un procédé qui permet de trouver tous les nombres premiers inférieurs à un certain entier naturel donné N. Le crible d'Atkin est plus rapide mais plus complexe.
L'algorithme procède par élimination : il s'agit de supprimer d'une table des entiers de 2 à N tous les multiples d'un entier (autres que lui-même).
En supprimant tous ces multiples, à la fin il ne restera que les entiers qui ne sont multiples d'aucun entier à part 1 et eux-mêmes, et qui sont donc les nombres premiers.
On commence par rayer les multiples de 2, puis les multiples de 3 restants, puis les multiples de 5 restants, et ainsi de suite en rayant à chaque fois tous les multiples du plus petit entier restant.
On peut s'arrêter lorsque le carré du plus petit entier restant est supérieur au plus grand entier restant, car dans ce cas, tous les non-premiers ont déjà été rayés précédemment.
À la fin du processus, tous les entiers qui n'ont pas été rayés sont les nombres premiers inférieurs à N.
L'animation ci-dessous illustre le crible d'Ératosthène pour N=120 :
Remarque: si un nombre n est composé, alors n=n1n2, avec nécessairement l'un au moins des diviseurs ni plus petit que . C'est pourquoi dans le crible ci-dessus où l'on a choisi 120 puisque 121=11², on s'arrête après avoir trouvé les multiples de 7.
Le crible d'Ératosthène peut être mis en œuvre de façon classique ou récursive, mais aussi sous la forme d'une méthode pipe-line.
Pseudo-code
Dans une version classique, on transcrit ainsi l'algorithme :
Fonction Eratosthène(Limite)
L = tableau de booléen de taille Limite, initialisé à Vrai
L[1] = Faux
Pour i de 2 à Limite
Si L[i]
Pour j de i*i à Limite par pas de i
on peut commencer à i*i car tous les multiples de i inférieurs à i*i ont déjà été rayés
L[j] = Faux
Fin pour
Fin si
Fin pour
Retourner L
Fin fonction
Comme dans l'animation ci-dessus, on peut optimiser le code précédent en arrêtant la boucle Pour i une fois i*i>Limite puisque l'on ne rentrera plus dans la boucle Pour j et en se contentant d'afficher les indices de L contenant Vrai.
Fonction Eratosthène(Limite)
L = tableau de booléen de taille Limite, initialisé à Vrai
L[1] = Faux
i=2
Tant que i*i≤Limite
Si L[i]
Pour j de i*i à Limite par pas de i
on peut commencer à i*i car tous les multiples de i inférieurs à i*i ont déjà été rayés
L[j] = Faux
Fin pour
Fin si
i=i+1
Fin tant que
Retourner L
Fin fonction
On peut aussi éviter de cocher plusieurs fois les nombres pairs et diviser le temps d'exécution par 2
Fonction Eratosthène(Limite)
L = tableau de booléen de taille Limite, initialisé à Vrai
Mettre à Faux les cases d'indice pair > 2
L[1] = Faux
i=3
Tant que i*i≤Limite
Si L[i]
Pour j de i*i à Limite par pas de 2*i
L[j] = Faux
Fin pour
Fin si
i=i+1
Fin tant que
Retourner L
Fin fonction
Version récursive
Le crible d'Ératosthène se code facilement avec une fonction récursive, qu'il suffit d'appeler initialement avec le tableau des entiers de 2 à N.
Voici un pseudo code :
FONCTION Eratosthène( entiers ) SI premier entier au carré > dernier entier ALORS AFFICHE entiers SINON AFFICHE premier entier EXECUTE Eratosthène( tous les entiers non multiples du premier entier ) FIN SI FIN FONCTION
L'algorithme récursif présente comme avantage de pouvoir être codé sur un langage ne supportant pas de structure de données de type liste.
Version pipe-line : le crible de Hoare (1978)
L'idée est d'engendrer chaque nombre à vérifier, pour le soumettre à un tri en cascade, ne conservant des entiers reçus que ceux qui sont premiers.
Pour cela, à chaque nombre premier repéré est associé un poste qui ne transmettra parmi ses successeurs que ceux qui ne sont pas ses multiples.
Ce système n'utilise pas de table ou de liste de nombres à traiter a priori, mais à tout moment un poste (cellule active ou coroutine) par nombre premier déjà reconnu.
Crible de C.A.R HOARE : Un GENERATEUR passe chaque entier de 2 à N au premier poste disponible(qu'il crée s'il n'existe pas). Pour chaque POSTE créé : * il conserve le premier entier qu'il reçoit, disons p, * puis il transmet au poste suivant (créé si besoin) tout entier reçu n non divisible par p.
Ainsi :
- 2 crée le poste 2
- 3 passe le poste 2 et crée le poste 3
- 4 est intercepté par le poste 2
- 5 passe les postes 2 et 3, et crée le poste 5
- 6 est intercepté par le poste 2
- 7 passe les postes 2, 3, 5, et crée le poste 7
- ...
- 36 est intercepté par le poste 2,
- 37 passe les postes 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, et crée le poste 37...
En régime de croisière, ce crible commence à vérifier la primalité de nouveaux nombres pendant qu'il poursuit ou achève la vérification de la primalité de nombres précédents.
Nous noterons, qu'à moins de disposer d'une machine parallèle avec processeurs, cette méthode est inefficace puisque chaque poste parcourt un nombre d'entiers de l'ordre de n.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
