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;
}
