Crible d'Eratosthene


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

Algorithme

L'algorithme procède par élimination : il s'agit de supprimer d'une table tous les multiples des entiers de 2 à N.

À 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'Eratosthène pour N=120 :

New Animation Sieve of Eratosthenes.gif


Voici, étape par étape, le détail de la mise en œuvre de l'algorithme pour N=20.

Étape 1. Écrivons la liste des nombres naturels compris entre 2 et 20

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20


Étape 2. On marque le nombre suivant non rayé de la liste, comme premier.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20


Étape 3. On raye dans la liste, tous les multiples du nombre que l'on vient d'entourer.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20


Étape 4. Si le carré du nombre suivant non rayé est inférieur à 20, alors on recommence à l'étape 2 sinon on déclare tous les entiers restants non rayés premiers.

Puisque 3 élevé au carré est inférieur à 20, on retourne à l'étape 2 :

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20


À l'étape 4, l'entier suivant non rayé 5 a un carré strictement supérieur à 20, on considère comme premiers tous les entiers suivants non rayés.

Résultat : Les entiers premiers compris entre 2 et 20 sont : 2, 3, 5, 7, 11, 13, 17, 19.

Pour obtenir les entiers premiers inférieurs à N=99, on raye dans l'ordre tous les multiples des nombres premiers p=2, 3, 5, 7, … à partir de p2 jusqu'à N. On s'arrête lorsque l'entier premier p suivant vérifie p2 > N (Si un entier non premier est strictement supérieur à \sqrt{N} alors il a au moins un diviseur inférieur à \sqrt{N} et aura donc déjà été rayé). On va donc aller jusqu'à p=9, parce que 102=100>99, et déclarer premiers tous les entiers non rayés suivants. On obtient la table suivante :

0 1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
30 31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 49
50 51 52 53 54 55 56 57 58 59
60 61 62 63 64 65 66 67 68 69
70 71 72 73 74 75 76 77 78 79
80 81 82 83 84 85 86 87 88 89
90 91 92 93 94 95 96 97 98 99

Exemple d'implémentation

Le crible d'Eratothè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 exemple de code en bash :

erat()
if (($1**2 > ${!#}));
then
    echo $@;
else
    a=$1; b="";
    while shift; (($#));
    do (($1%$a)) && b+=" "$1;
    done;
    echo $a $(erat $b);
fi
 
erat {2..1000}

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

Liens externes

  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Crible d%27%C3%89ratosth%C3%A8ne ».

Wikimedia Foundation. 2010.

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

Regardez d'autres dictionnaires:

  • 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

  • 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 Algorithme 2 Exemples d… …   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”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.