Introduction
Tu as acheté une grande boîte de pièces d'ordinateur en vrac lors d'un vide-grenier.
Tu as commencé à assembler les pièces pour construire des ordinateurs sur mesure.
Tu veux tester les performances de différentes combinaisons de pièces, et tu décides de créer ton propre programme de test de performances pour comparer tes ordinateurs.
Tu choisis le fameux algorithme du « crible d'Ératosthène », un algorithme ancien, mais qui devrait pousser tes ordinateurs à leurs limites.
Instructions
Ta tâche consiste à créer un programme qui implémente l'algorithme du crible d'Ératosthène pour trouver tous les nombres premiers inférieurs ou égaux à un nombre donné.
Un nombre premier est un nombre supérieur à 1 qui n'est divisible que par 1 et par lui-même.
Par exemple, 2, 3, 5, 7, 11 et 13 sont des nombres premiers.
En revanche, 6 n'est pas un nombre premier, car il est non seulement divisible par 1 et par lui-même, mais aussi par 2 et par 3.
Pour utiliser le crible d'Ératosthène, tu commences par créer un tableau contenant tous les nombres entre 2 et le nombre donné.
Ensuite, tu répètes les étapes suivantes :
- Trouve le prochain nombre non marqué dans ton tableau (en sautant les nombres marqués).
C'est un nombre premier.
- Marque tous les multiples de ce nombre premier comme non premiers.
Tu répètes ces étapes jusqu'à avoir parcouru tous les nombres de ton tableau.
À la fin, tous les nombres non marqués sont premiers.
Les tests ne vérifient pas que tu as implémenté l'algorithme, seulement que tu as produit la bonne liste de nombres premiers.
Pour vérifier que tu implémentes correctement le crible, un bon premier test consiste à vérifier que tu n'utilises ni division ni opération de reste.
Exemple
Supposons que tu cherches les nombres premiers inférieurs ou égaux à 10.
- Écris la liste 2, 3, 4, 5, 6, 7, 8, 9, 10, en les laissant tous non marqués.
- 2 n'est pas marqué, c'est donc un nombre premier.
Marque 4, 6, 8 et 10 comme « non premier ».
- 3 n'est pas marqué, c'est donc un nombre premier.
Marque 6 et 9 comme non premier (marquer 6 est facultatif, puisqu'il a déjà été marqué).
- 4 est marqué comme « non premier », donc on le saute.
- 5 n'est pas marqué, c'est donc un nombre premier.
Marque 10 comme non premier (facultatif, puisqu'il a déjà été marqué).
- 6 est marqué comme « non premier », donc on le saute.
- 7 n'est pas marqué, c'est donc un nombre premier.
- 8 est marqué comme « non premier », donc on le saute.
- 9 est marqué comme « non premier », donc on le saute.
- 10 est marqué comme « non premier », donc on s'arrête, car il n'y a plus de nombres à vérifier.
Tu as examiné tous les nombres et constaté que 2, 3, 5 et 7 ne sont toujours pas marqués, ce qui signifie qu'ils sont les nombres premiers inférieurs ou égaux à 10.
