Le crible d'Ératosthène est une méthode ancienne et efficace pour trouver tous les nombres premiers jusqu'à un certain nombre entier $n$. Un nombre premier est un nombre qui a exactement deux diviseurs distincts : 1 et lui-même.

Étapes du crible d'Ératosthène

1. Liste de départ : Écrivez tous les nombres entiers de 2 jusqu'à $n$. Par exemple, si $n = 10$, vous écrivez : 2, 3, 4, 5, 6, 7, 8, 9, 10.

2. Premier nombre premier : Le premier nombre de la liste (2) est un nombre premier.

3. Élimination des multiples : Barrez tous les multiples de 2 (le premier nombre premier) dans la liste, sauf 2 lui-même.

4. Prochain nombre premier : Le prochain nombre non barré dans la liste après 2 est 3. Répétez le processus pour 3 : barrez tous les multiples de 3 dans la liste, sauf 3 lui-même.

5. Répéter le processus : Continuez de cette manière : le prochain nombre non barré est le prochain nombre premier. Barrez tous ses multiples de la liste.

6. Arrêt : Arrêtez-vous quand vous avez passé la racine carrée de $n$ ou quand tous les multiples du dernier nombre premier trouvé ont été barrés. Les nombres restants non barrés dans la liste sont tous premiers.

Exemple pratique

Prenons un exemple simple : trouver tous les nombres premiers jusqu'à 100.

• Barrez le 1.

• Barrez les multiples de 2 (hormis 2).

• Barrez les multiples de 3 (hormis 3).

• Continuez avec 5 et les nombres suivants jusqu'à la racine carrée de 100 soit 10.

Les nombres qui restent non barrés sont les nombres premiers jusqu'à 100.