Se connecter
ou

Le crible d'Érathostène

Le crible d'Eratosthène permet de trouver tous les nombres premiers plus petits qu'un entier naturel N prédéfini.

À l'aide du crible d'Eratosthène, déterminer tous les nombres premiers inférieurs à 100.

Etape 1

Écrire la liste de tous les nombres inférieurs à N

On dresse, sous forme de tableau par exemple, la liste de tous les nombres inférieurs à N.

On dresse la liste de tous les entiers inférieurs ou égaux à 100.

-
Etape 2

Éliminer 1

1 n'est pas un nombre premier, on le barre.

On barre le 1 qui n'est pas un nombre premier.

-
Etape 3

Entourer 2 et éliminer les multiples de 2

2 est le premier nombre premier, on l'entoure.

Tous les multiples de 2 ne peuvent donc pas être premiers, on les barre.

On entoure le 2 et on barre les multiples de 2.

-
Etape 4

Entourer 3 et éliminer les multiples de 3

Dans le tableau, on sélectionne le premier nombre suivant qui n'a pas été barré. Ce nombre est premier. Ici, 3 est le nombre premier suivant, on l'entoure.

Tous les multiples de 3 ne peuvent donc pas être premiers, on les barre.

On entoure le 3 et on barre les multiples de 3.

-
Etape 5

Entourer 5 et éliminer les multiples de 5

Dans le tableau, on sélectionne le premier nombre suivant qui n'a pas été barré. Ce nombre est premier. Ici, 5 est le nombre premier suivant, on l'entoure.

Tous les multiples de 5 ne peuvent donc pas être premiers, on les barre.

À l'aide de la liste, le nombre premier suivant est le 5. On l'entoure et on barre les multiples de 5.

-
Etape 6

Renouveler le procédé jusqu'à la partie entière de \(\displaystyle{\sqrt N}\)

On réitère le procédé avec tous les nombres premiers inférieurs ou égaux à \(\displaystyle{\sqrt N}\).

À l'aide de la liste, le nombre premier suivant est le 7. On l'entoure et on barre les multiples de 7.

Ensuite le nombre premier suivant est le 11. Or \(\displaystyle{11 \gt \sqrt {100}}\).

Donc on s'arrête là.

-
Etape 7

Conclure

On conclut en donnant la liste des nombres non barrés de la liste : ce sont les nombres premiers inférieurs à N.

Les nombres premiers inférieurs à 100 sont donc :

\(\displaystyle{2-3-5-7-11-13-17-19-23-29-31-37-41-\\43-47-53-59-61-67-71-73-79-83-89-97}\)