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]