Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

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. On forme une table avec tous les entiers naturels compris entre 2 et N et on raye les uns après les autres, les entiers qui ne sont pas premiers de la manière suivante : dès que l'on trouve un entier qui n'a pas encore été rayé, il est déclaré premier, et on raye tous les autres multiples de celui-ci.

Étudions un exemple et déterminons la liste de tous les nombres premiers inférieurs à 20.

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

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

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

É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 :

À 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 jusqu'à N. On s'arrête lorsque l'entier premier p suivant vérifie (Si un entier non premier est strictement supérieur à alors il a au moins un diviseur inférieur à et aura donc déjà été rayé). On va donc aller jusqu'à p=9, parce que 10²=100>99, et déclarer premiers tous les entiers non rayés suivants. On obtient la table suivante :

Voir aussi: nombre premier