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.

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 :

Exemples d'implémentation

Le crible d'Ératosthène peut être implémenté de façon classique ou récursive.

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

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.

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.

Liens internes

• Crible d'Atkin
• Spirale d'Ulam

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.