Crible d'Ératosthène

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[modifier | modifier le code]

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 :

New Animation Sieve of Eratosthenes.gif

Exemples de mise en œuvre[modifier | modifier le code]

Le crible d'Ératosthène peut être mis en œuvre de façon classique ou récursive.

Pseudo-code[modifier | modifier le 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[modifier | modifier le code]

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.

Notes et références[modifier | modifier le code]

Source[modifier | modifier le code]

Κόσκινον Ερατοσθένους 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.

Annexes[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]