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. L’algorithme procède par élimination : il s’agit de trouver le premier entier non supprimé puis supprimer tous ses multiples, à l’exception de lui même. À la fin, il ne restera que les nombres premiers. Par exemple, pour n = 20, on obtient à la fin l’ensemble des nombres premiers compris entre 2 et 19.
On va utiliser un tableau de booléens (VRAI/1 ou FAUX/0) pour l'implémentation de cet algorithme. On initialise le tableau à VRAI sauf pour les positions 0 et 1 car ni 0 ni 1 ne sont premiers.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| F | F | V | V | V | V | V | V | V | V | V | V | V | V | V | V | V | V | V | V |
On cherche la position de la première case à VRAI : 2. On met à FAUX tous les multiples de 2 strictement supérieurs à 2.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| F | F | V | V | F | V | F | V | F | V | F | V | F | V | F | V | F | V | F | V |
On cherche la position de la première case à VRAI après 2 : 3. On met à FAUX tous les multiples de 3 strictement supérieurs à 3.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| F | F | V | V | F | V | F | V | F | F | F | V | F | V | F | F | F | V | F | V |
On continue jusqu’à ce qu’il n’y ait plus de prochaine case à VRAI. Le tableau est donc complet : chaque position à VRAI est un nombre premier.
init() marche aussi avec un tableau à allouer dynamiquementstdout, les nombres du tableau dont la valeur est VRAI. Il n'est pas demandé d'ouvrir le fichier.listeNombrePremiers() renvoie le nombre de nombres premiers de la liste (en plus de l'affichage de cette liste)L'affiche de la liste des nombres se fait avec un seul espace entre les nombres. La chaine n'a pas d'espace à la fin.