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

Ce document intitulé « Vérifier si un nombre entier est un nombre premier en C » issu de CommentCaMarche (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.