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.
Les nombres marqués sont les nombres premiers jusqu’à 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.
Note historique
À l’époque où Archimède étudiait les mathématiques à Syracuse, un autre mathématicien de talent s’était joint au personnel du Musée d’Alexandrie, en Égypte, à la demande du pharaon Ptolémée III : Ératosthène de Cyrène (la Libye d’aujourd’hui). À la fois poète, historien, géographe, astronome, athlète et mathématicien, il a été le précepteur du fils du pharaon et bibliothécaire en chef de l’université d’Alexandrie.