Exercice langage C: Le Crible d'Ératosthène

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 à .
• 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:

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; isupprimes[i] = false;
for (int i=2; iif (!supprimes[i]) {
int multiple = 2 * i;
while (multiple supprimes[multiple] = true;
multiple += i;
}
}
for (int i=0; iif (!supprimes[i])
cout cout return 0;
}