Vérifier si un nombre entier est un nombre premier en C
- 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;
}
Ce document intitulé « Vérifier si un nombre entier est un nombre premier en C » issu de Comment Ça Marche (www.commentcamarche.net) est mis à disposition sous les termes de la licence Creative Commons. Vous pouvez copier, modifier des copies de cette page, dans les conditions fixées par la licence, tant que cette note apparaît clairement.
