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:

  bool supprimes[100];

pour mémoriser les entiers qui ont été supprimés. N'oubliez pas d'initialiser chacun de ses éléments à false.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#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;
}