Vérifier si un nombre entier est un nombre premier en C
[Dal]
Messages postés
6205
Date d'inscription
Statut
Contributeur
Dernière intervention
-
Note : lami20j est l'auteur d'origine de l'astuce.
- Définition nombre premier
- Algorithme 1 : les diviseurs compris entre 2 et N-1 seront testés
- Algorithme 2 : les diviseurs pairs ne seront pas testés, la recherche se limitant aux diviseurs impairs
- Algorithme 3 : les diviseurs impairs jusqu'à la racine carrée du N seront testés
- Algorithme4 : arrêt du programme quand un diviseur est trouvé
Définition nombre premier
Un nombre premier est un entier naturel, qui se divise seulement par 1 et lui-même.Algorithme 1 : les diviseurs compris entre 2 et N-1 seront testés
- les diviseurs compris entre 2 et N-1 seront testés
/**************************\ * nombre_premier1.c * \**************************/ /* algorithme : teste tous les diviseurs */ #include <stdio.h> int main (void) { int i, nb, compter, test; test = compter = 0; printf ("Entrez un nombre entier : "); if (scanf ("%d", &nb) != 1) return -1; for (i = 2; i < nb; i++, compter++) if (nb % i == 0) test = 1; if (!test) printf ("%d nombre premier, nombre iterations = %d\n", nb, compter); else printf ("%d n'est pas nombre premier, nombre iterations = %d\n", nb,compter); return 0; }
Algorithme 2 : les diviseurs pairs ne seront pas testés, la recherche se limitant aux diviseurs impairs
- les diviseurs pairs ne seront pas testés, la recherche se limitant aux diviseurs impairs
/**************************\ * nombre_premier2.c * \**************************/ /* algorithme : exclure les nombres pairs et * teste tous les diviseurs */ #include <stdio.h> int main (void) { int i, nb, compter, test; test = compter = 0; printf ("Entrez un nombre entier : "); if (scanf ("%d", &nb) != 1) return -1; if (nb % 2 == 0) test = 1; else{ for (i = 3 ; i < nb; i+=2, compter++) if (nb % i == 0) test = 1; } if (!test) printf ("%d nombre premier, nombre iterations = %d\n", nb, compter); else printf ("%d n'est pas nombre premier, nombre iterations = %d\n",nb, compter); return 0; }
Algorithme 3 : les diviseurs impairs jusqu'à la racine carrée du N seront testés
- les diviseurs impairs jusqu'à la racine carrée du N seront testés
/**************************\ * nombre_premier3.c * \**************************/ /* algorithme : exclure les nombres pairs et * teste tous les diviseurs jusqu'à la racine carrée */ #include <stdio.h> #include <math.h> int main (void) { int i, nb, compter, test,limite; test = compter = 0; printf ("Entrez un nombre entier : "); if (scanf ("%d", &nb) != 1) return -1; limite = sqrt(nb) + 1; if (nb % 2 == 0) test = 1; else{ for (i = 3 ; i < limite; i+=2, compter++) if (nb % i == 0) test = 1; } if (!test) printf ("%d nombre premier, nombre iterations = %d\n", nb, compter); else printf ("%d n'est pas nombre premier, nombre iterations = %d\n",nb, compter); return 0; }
Algorithme4 : arrêt du programme quand un diviseur est trouvé
- arrêt du programme quand un diviseur est trouvé
/**************************\ * nombre_premier4.c * \**************************/ /* algorithme : exclure les nombres pairs et * teste tous les diviseurs jusqu'à la racine carrée * et sortie de la boucle au 1er diviseur trouvé */ #include <stdio.h> #include <math.h> int main (void) { int i, nb, compter, test,limite; test = compter = 0; printf ("Entrez un nombre entier : "); if (scanf ("%d", &nb) != 1) return -1; limite = sqrt(nb) + 1; if (nb % 2 == 0) test = 1; else{ for (i = 3 ; i < limite && ! test; i+=2, compter++) if (nb % i == 0) test = 1; } if (!test) printf ("%d nombre premier, nombre iterations = %d\n", nb, compter); else printf ("%d n'est pas nombre premier, nombre iterations = %d\n", nb, compter); return 0; }