Crible d'Ératosthène

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

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 :

New Animation Sieve of Eratosthenes.gif

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

Références et liens externes



Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Crible d'Ératosthène de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Crible d'Eratosthene — 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 1… …   Wikipédia en Français

  • Crible d'Eratosthène — 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 1… …   Wikipédia en Français

  • Crible d’Ératosthène — 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 1… …   Wikipédia en Français

  • Eratosthene — Ératosthène Pour Ératosthène, un des 30 oligarques s étant emparés du pouvoir à Athènes après la guerre du Péloponnèse, voir l article Les Trente. Ératosthène Naissance 276 Cyrène (Libye) …   Wikipédia en Français

  • Eratosthène — Ératosthène Pour Ératosthène, un des 30 oligarques s étant emparés du pouvoir à Athènes après la guerre du Péloponnèse, voir l article Les Trente. Ératosthène Naissance 276 Cyrène (Libye) …   Wikipédia en Français

  • crible — [ kribl ] n. m. • fin XIIIe; lat. pop. criblum, class. cribrum 1 ♦ Instrument percé d un grand nombre de trous, et qui sert à trier des objets de grosseur inégale. ⇒ claie, grille, passoire, sas, tamis. Passer au crible. ⇒ cribler. Crible… …   Encyclopédie Universelle

  • Crible d'Erathostene — 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 1… …   Wikipédia en Français

  • Crible d'Erathostène — 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 1… …   Wikipédia en Français

  • Crible d'Érathostène — 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 1… …   Wikipédia en Français

  • Crible d’Atkin — Crible d Atkin Le crible d Atkin est un procédé qui permet de trouver tous les nombres premiers inférieurs à un certain entier naturel donné N. C est une version améliorée du crible d Ératosthène, il fut créé en 1999 par A. O. L. Atkin et Daniel… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”