Crible d'Ératosthène
Algorithme qui permet de trouver les nombres premiers inférieurs à un nombre donné.
Cet algorithme est décrit par la suite d'instructions ci-dessous :
Pour trouver tous les nombres premiers jusqu'à un nombre n donné :
- écrire dans un tableau la liste de tous les nombres naturels de 1 à n;
- éliminer le 1 qui n'est pas un nombre premier;
- marquer 2 et éliminer tous les multiples de 2;
- faire de même avec 3;
- choisir le plus petit nombre non souligné et non éliminé (ici 5);
- éliminer tous ses multiples;
- réitérer le procédé jusqu'à la partie entière de la racine carrée de n.
Exemple
Si on désire trouver tous les nombres premiers inférieurs à 50, on doit d'abord déterminer la partie entière de la racine carrée de 50 : il s'agit de 7, car la racine carrée de 50 est environ 7,07.On élimine d’abord le nombre 1. On élimine les multiples de 2 sauf 2. On élimine les multiples de 3 sauf 3. On élimine les multiples de 5 sauf 5. On élimine les multiples de 7 sauf 7.
Les nombres encerclés sont ceux qui restent et sont les nombres premiers inférieurs à 50.