Test de primalité

, par Pierre

Sujet

Écrire un programme qui demande à l’utilisateur d’entrer un nombre entier positif n, teste si n est premier puis affiche le résultat.

Solution

Un nombre est premier s’il est divisible seulement par 1 et par lui même.

Comme un nombre différent de 0 n’est jamais divisible par un nombre plus grand que lui-même, il suffit de tester si n est divisible par 2, ..., n -1. Si aucun de ces nombres ne divise n, n est premier.

On utilise un while qui simule le fonctionnement d’un for (d = 2 ; d < n ; d = d + 1) en ajoutant un cas d’arrêt prématuré de la boucle si n s’avère divisible par d.

  1. /* Declaration de fonctionnalites supplementaires */
  2. #include <stdlib.h> /* pour EXIT_SUCCESS */
  3. #include <stdio.h> /* pour printf() */
  4.  
  5. /* Declaration des constantes et types utilisateur */
  6. #define TRUE 1
  7. #define FALSE 0
  8.  
  9. /* Declaration des fonctions utilisateur */
  10.  
  11. /* Fonction principale */
  12. int main()
  13. {
  14.     /* Declaration et initialisation des variables */
  15.     int n = 1;
  16.     int d;
  17.     int premier = TRUE;
  18.  
  19.     printf("Donner un entier positif (0 pour terminer)\n");
  20.     scanf("%d", &amp;n);
  21.     printf("Vous avez saisi %d\n", n);
  22.    
  23.     /* test de primalité */
  24.     d = 2;
  25.     while ( premier &amp;&amp; (d < n - 1) )
  26.     {
  27.         if (n % d == 0)
  28.         {
  29.             printf("divisible par %d\n", d);
  30.             premier = FALSE;
  31.         }
  32.         d = d + 1;
  33.     }
  34.    
  35.     if (premier)
  36.     {
  37.         printf("%d est premier\n", n);
  38.     }
  39.     else
  40.     {
  41.         printf("%d n'est  pas premier\n", n);
  42.     }
  43.     /* Valeur fonction */
  44.     return EXIT_SUCCESS;
  45. }
  46.  
  47. /* Definition des fonctions utilisateur */

Télécharger

Revenu et logement, Je livre ici quelques éléments de comparaison concernant mon niveau de vie, pour couper court à quelques idées reçues, et un condensé de nombreuses (...)
Revenu et travail d’un enseignant-chercheur, Cet article complète l'article Revenu et logement, en détaillant un peu le budget de mon ménage, mon parcours d'enseignant-chercheur en terme de (...)
Cybersyn (el systemo synco), Au café, mardi 5 avril 2011, j'ai bien vu que, mis à part Antoine Allombert, personne ne connaissait l'histoire de l'extraordinaire projet chilien (...) [jpg, jpg, png]