Le menu est disponible grâce au bouton Le crible d’Ératosthène
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.
Notes sur le travail à réaliser
- Le test INIT1 permet de vérifier l'initialisation d'un tableau statique avec tous ses éléments à VRAI sauf les deux premiers qui sont égaux à FAUX
- Le test INIT2 vérifie que la fonction
init()marche aussi avec un tableau à allouer dynamiquement - Le test AFF1 affiche dans un fichier, par exemple la sortie standard
stdout, les nombres du tableau dont la valeur est VRAI. Il n'est pas demandé d'ouvrir le fichier. - Le test SUPP2 affiche le même tableau lorsque les multiples de 2 sont supprimés
- Le test SUPP3 affiche le même tableau lorsque les multiples de 3 sont supprimés
- Le test SUPP2_3 affiche le même tableau lorsque les multiples de 2 et de 3 sont supprimés
- Le test PROCHAIN permet de donner le prochain nombre à VRAI dans le tableau
- Les tests FINAL? permettent de bien vérifier que les différentes étapes du crible ont été respectées et que la liste des nombres premiers est correcte. La fonction
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.