Exercice langage C: Le Crible d'Ératosthène
Rédigé par BENKIRANE Fatima Ezzahra, Publié le 17 Mars 2012, Mise à jour le Lundi, 07 Novembre 2022 10:48Un 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 à .
- L'entier 5 n'a pas été supprimé, il est donc premier. Supprimons tous les multiples de 5 inférieurs à .
- 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.
#include
using namespace std;
int main(int argc, char **argv)
{
bool supprimes[100];
supprimes[0] = true; // 0 n'est pas premier
supprimes[1] = true; // 1 n'est pas premier
for (int i=2; i<100; i++)
supprimes[i] = false;
for (int i=2; i<100; i++)
if (!supprimes[i]) {
int multiple = 2 * i;
while (multiple < 100) {
supprimes[multiple] = true;
multiple += i;
}
}
for (int i=0; i<100; i++)
if (!supprimes[i])
cout << i << " ";
cout << endl;
return 0;
}