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 à écrire 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 n'est pas seulement divisible par 1 et par lui-même, mais aussi par 2 et par 3.
Pour utiliser le crible d'Ératosthène, commence par écrire tous les nombres de 2 jusqu'au nombre donné inclus.
Ensuite, suis ces étapes :
- Trouve le prochain nombre non marqué (en sautant les nombres marqués).
Ce nombre est premier.
- Marque tous les multiples de ce nombre premier comme non premiers.
Répète ces étapes jusqu'à ce que tu aies parcouru tous les nombres.
À la fin, tous les nombres non marqués sont premiers.
Le crible d'Ératosthène marque les multiples de chaque nombre premier en utilisant l'addition (ajouter le nombre premier de façon répétée) ou la multiplication (calculer directement ses multiples), plutôt que de vérifier la divisibilité de chaque nombre.
Les tests ne vérifient pas que tu as implémenté l'algorithme, seulement que tu as trouvé les bons nombres premiers.
Exemple
Imaginons que tu cherches les nombres premiers inférieurs ou égaux à 10.
-
Écris 2, 3, 4, 5, 6, 7, 8, 9, 10, sans en marquer aucun.
2 3 4 5 6 7 8 9 10
-
2 n'est pas marqué, c'est donc un nombre premier.
Marque 4, 6, 8 et 10 comme « non premiers ».
2 3 [4] 5 [6] 7 [8] 9 [10]
↑
-
3 n'est pas marqué, c'est donc un nombre premier.
Marque 6 et 9 comme non premiers (marquer 6 est facultatif, puisqu'il a déjà été marqué).
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
4 est marqué comme « non premier », donc on le saute.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
5 n'est pas marqué, c'est donc un nombre premier.
Marque 10 comme non premier (facultatif, puisqu'il a déjà été marqué).
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
6 est marqué comme « non premier », donc on le saute.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
7 n'est pas marqué, c'est donc un nombre premier.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
8 est marqué comme « non premier », donc on le saute.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
9 est marqué comme « non premier », donc on le saute.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
10 est marqué comme « non premier », donc on s'arrête, car il n'y a plus de nombres à vérifier.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
Tu as examiné tous les nombres et tu as constaté que 2, 3, 5 et 7 ne sont toujours pas marqués, ce qui signifie que ce sont les nombres premiers inférieurs ou égaux à 10.
