est_premier

est_premier.c

/* est_premier: indique si un nombre entier est premier ou non */

#include `<stdbool.h>`

#include "entier_nat.h"
#include "egal.h"

/* Profil:

 * -------
 *  entier_nat -> booleen
 *
 * Exemples:
 * ---------
 *
 *  est_premier(2)?
 *     2 divise 2 et 2 egale 2 -> 2 premier
 *
 *  est_premier(4)?
 *     2 divise 4 et 2 different de 4 -> 4 non premier
 *
 *  est_premier(35)?
 *     2 ne divise pas 35
 *  et 3 ne divise pas 35
 *  et 4 ne divise pas 35
 *  et 5 divise 35
 *     5 non egale a 35
 *     35 non premier
 *
 *  Il faut passer par une fonction auxiliaire
 *
 *  aux: entier_nat x entier_nat -> booleen
 *
 * Axiomes:
 * --------
 *
 *  est_premier(0) = faux
 *  est_premier(1) = faux
 *  est_premier(succ(succ(a))) = aux(2, succ(succ(a)))
 *
 *  aux(a, b) = egal(a, b) ou non (divise(a, b) ou aux(succ(a), b))
 *
 * Algorithme recursif:
 * --------------------
 *  fonction est_premier(a: entier_nat): booleen
 *  debut
 *   | si egal(0,a)
 *   |  | alors retourner faux
 *   |  | sinon si egal(1, a)
 *   |  |        | alors retourner faux
 *   |  |        | sinon retourner aux(2, a)
 *   |  |       finsi
 *   | finsi
 *  fin
 *
 *  fonction aux(a: entier_nat, b: entier_nat): booleen
 *  debut
 *     si egal(a, b)
 *      | alors retourner vrai
 *      | sinon si divise(a, b)
 *      |        | alors retourner faux
 *      |        | sinon retourner aux(succ(a), b)
 *      |       finsi
 *     finsi
 *  fin
 *
 * Algorithme iteratif:
 * --------------------
 *  fonction est_premier(a: entier_nat): booleen
 *  debut
 *   | si egal(0,a)
 *   |  | alors retourner faux
 *   |  | sinon si egal(1, a)
 *   |  |        | alors retourner faux
 *   |  |        | sinon 
 *   |  |        |    b: entier_nat
 *   |  |        |    b := 2
 *   |  |        |    tant que (non divise(b, a)) faire
 *   |  |        |     | b = b+1
 *   |  |        |    fintantque
 *   |  |        |    si egal(b, a)
 *   |  |        |     | alors retourner vrai
 *   |  |        |     | sinon retourner faux
 *   |  |        |    finsi
 *   |  |       finsi
 *   | finsi
 *  fin
 */ 
bool aux(ENTIER_NAT a, ENTIER_NAT b)
{
   if (egal_recursif(a, b))
   {
      return true;
   }
   else 
   {
      if (b%a == 0)
      {
         return false;
      }
      else
      {
         return aux(succ(a), b);
      }
   }
}

bool est_premier_recursif(ENTIER_NAT a)
{
   if (a == 0)
   {
      return false;
   }
   else if (a == 1)
   {
      return false;
   }
   else
   {
      return aux(2, a);
   }
}

bool est_premier_iteratif(ENTIER_NAT a)
{
   if (a == 0)
   {
      return false;
   }
   else if (a == 1)
   {
      return false;
   }
   else
   {
      int b;
      b = 2;
      while (a%b != 0)
      {
         b = b+1;
      }
      if (a == b)
      {
         return true;
      }
      else
      {
         return false;
      }
   }
}

int main()
{
   int i;
   for (i = 0; i <= 20; i = i+1)
   {
      if (est_premier_recursif(i))
      {
         printf("%d est premier\n", i);
      }
      else
      {
         printf("%d n'est pas premier\n", i);
      }
   }
   for (i = 0; i <= 20; i = i+1)
   {
      if (est_premier_iteratif(i))
      {
         printf("%d est premier\n", i);
      }
      else
      {
         printf("%d n'est pas premier\n", i);
      }
   }
}