Admin CliCours
Exercice corrigé, tutoriel langage C.
Un nombre est dit premier s’il admet exactement 2 diviseurs distincts (1 et lui-même). 1 n’est donc pas premier.
Le crible d’Ératosthène une méthode de recherche des nombres premiers plus petits qu’un entier naturel donné. La méthode est simple:
- On commence par supprimer tous les multiples de 2 inférieurs à .
- L’entier 3 n’a pas été supprimé et il ne peut être multiple des entiers qui le précèdent, sinon on l’aurait supprimé; il est donc premier. Supprimons alors tous les multiples de 3 inférieurs à n
- L’entier 5 n’a pas été supprimé, il est donc premier. Supprimons tous les multiples de 5 inférieurs à n
- Et ainsi de suite jusque . Les valeurs n’ayant pas été supprimées sont les nombres entiers plus petits que .
Écrivez le code qui applique cette méthode pour trouver les nombres premiers inférieurs à 100. Vous devez trouver: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
On utilisera un tableau de booléens:
bool supprimes[100];
pour mémoriser les entiers qui ont été supprimés. N’oubliez pas d’initialiser chacun de ses éléments à false.
La correction exercice C/C++ (voir page 2 en bas)
