Exercice langage C corrigé le crible d’Eratosthène

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)

Télécharger aussi :

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *