Vérifier si un nombre entier est un nombre premier en C

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