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.
Algorithme
L'algorithme procède par élimination : il s'agit de supprimer d'une table des entiers de 2 à N tous les multiples d'un entier (autres que lui-même).
En supprimant tous ces multiples, à la fin il ne restera que les entiers qui ne sont multiples d'aucun entier à part 1 et eux-mêmes, et qui sont donc les nombres premiers.
On commence par rayer les multiples de 2, puis les multiples de 3 restants, puis les multiples de 5 restants, et ainsi de suite en rayant à chaque fois tous les multiples du plus petit entier restant.
On peut s'arrêter lorsque le carré du plus petit entier restant est supérieur au plus grand entier restant, car dans ce cas, tous les non-premiers ont déjà été rayés précédemment (si un nombre n n'est pas entier il peut s'écrire sous la forme n=n1n2, avec nécessairement l'un au moins des diviseurs ni plus petit que . )
À la fin du processus, tous les entiers qui n'ont pas été rayés sont les nombres premiers inférieurs à N.
Sources:
https://fr.wikipedia.org/wiki/Crible_d%27%C3%89ratosth%C3%A8ne