Crible d'Ératosthène
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. C'est l'ancêtre du crible d'Atkin qui est plus rapide mais plus complexe.
Sommaire |
[modifier] Algorithme
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. En supprimant tous les multiples, à la fin il ne restera que les entiers qui ne sont multiples d'aucun entier, et qui sont donc les nombres premiers.
On commence par rayer les multiples de 2, puis à chaque fois on raye 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 :
[modifier] Exemples d'implémentation
Le crible d'Ératosthène peut être implémenté de façon classique ou récursive.
[modifier] Pseudo-code
Dans une version classique, on transcrit ainsi l'algorithme :
Fonction Eratosthène(Limite)
L = liste des entiers de 2 à Limite
Tant que L est non vide
Afficher le premier entier de L
L = liste des entiers de L non multiples du premier
Fin tant que
Fin fonction
[modifier] Version récursive
Le crible d'Ératosthène s'implémente 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 implémenté sur un langage ne supportant pas de structure de données de type liste.
[modifier] Notes et références
Κόσκινον Ερατοσθένους or, The Sieve of Eratosthenes. Being an Account of His Method of Finding All the Prime Numbers, by the Rev. Samuel Horsley, F. R. S., Philosophical Transactions (1683-1775), Vol. 62. (1772), pp. 327-347.
[modifier] Liens internes
[modifier] Références et liens externes
- (fr) Implémentation en C# d'une optimisation du crible d'Ératosthène
- (fr) [1], des applets java simulant le crible d'Ératosthène.
