Fonctions arithmétiques : estpremier, factorise, pgcd, nbrarrangement, ... (en c)

Commenter

Contenu du snippet

Fonctions arithmétiques programmées par Haypo :
- Test de primalité
- Recherche du prochain nombre premier
- Factorisation d'un nombre
- Pgcd/ppcm
- Somme/produit (des nombres entiers naturels de a à b)
- Factoriel (x!)
- NbrArr/NbrComb (nombre d'arrangement: nCr, et nombre de combinaisons: nPr)

Source / Exemple : 


/*
  Fonctions arithmétiques programmées par Haypo :
  - Test de primalité
  - Recherche du prochain nombre premier
  - Factorisation d'un nombre
  - Pgcd/ppcm
  - Somme/produit (des nombres entiers naturels de a à b)
  - Factoriel (x!)
  - NbrArr/NbrComb (nombre d'arrangement: nCr, et nombre de combinaisons: nPr)

  -------
  Haypo :
  -------
  haypo@ifrance.com
  http://www.haypocalc.com/ : HaypoCALC, calculatrice formelle en C++
  http://www.developpez.com/pascal/ : Programmation Turbo Pascal DOS


  • /


#include "stdio.h"	// printf
#include <math.h> // floor, sqrt, ...

typedef enum 
{
  false,
  true
} bool;

#ifdef linux
  void clrscr ()
  {
    // Utilise ANSI
    printf ("\x1B[2J\x1B[0;0H");    
  }
#else
  #include "conio.h"
#endif

// Définit le type des nombres entiers relatifs
typedef long NombreZ;

// Définit le type des nombres réels
typedef double NombreR;
/******************************************************************************/
  // Valeur absolue d'un nombre
inline NombreZ Abs (NombreZ x)
{
  return (x<0?-x:x);
}

/******************************************************************************/
  // Dit si un nombre est premier ou non
bool EstPremier (NombreZ x) {
  NombreZ i=2;

  // Inférieur à 2 : pas premier
  if (x<2) return false;

  // Egal à 2 : premier
  if (x==2) return true;

  // Teste tous les diviseur inférieur au nombre (de 2 à x-1)
  i=2;
  while (i<x) {
    // Si on peut diviser ce nombre : il n'est pas premier
    if (x % i == 0) return false;

    // Passe au prochain diviseur
    i++;
  }

  // Aucun ne le divise : il est premier
  return true;
}
/******************************************************************************/
  // Cherche le prochain nombre premier
NombreZ ProchainPremier (NombreZ x) {
  // Inférieur à 3 : le prochain est 2
  if (x<3) return 2;

  // Nombre pair : passe au nombre impair (le seul premier pair est 2)
  if (x % 2==0) x++;

  // Incrémente x de 2 jusqu'à ce qu'il soit premier
  while (!EstPremier(x)) x += 2;

  // Retourne x
  return x;
}
/******************************************************************************/
  // Racine carré d'un nombre réel
NombreR RacineCarre (NombreR x) 
{  
  return sqrt(x);
}
/******************************************************************************/
  // Renvoie l'entier inférieur d'un nombre réel
NombreZ EntierInf (NombreR x) {  
  return (NombreZ)floor(x);
}
/******************************************************************************/
  // Affiche la factorisation d'un nombre entier en produit de facteurs
  // premiers (puis revient à la ligne)
void AfficheFactorisation (NombreZ x)
{
  NombreZ
    DiviseurPremier,      // Diviseur premier (2,3,5,7,11,13,...)
    exposant,		  // Exposant d'un diviseur premier
    RacineX,		  // Racine carrée de X
    SauveX,               // Sauve la valeur de X
    NbrFacteur;           // Nombre de facteur

  // Nombre compris entre 0 et 4 ? Pas besoin de factoriser
  if ((0<=x) && (x<4)) {
    printf ("%ld\n",x);
    return;
  }

  DiviseurPremier=2;     // Diviseur premier (2,3,5,7,11,13,...)
  SauveX=x;              // Sauve la valeur de X
  NbrFacteur=0;	         // Nombre de facteur

  // Nombre négatif ? Factorise l'opposé
  if (x<0) {
    printf ("-");
    x = -x;
  }
  
  // Calcule la racine carrée de X
  RacineX = EntierInf (RacineCarre (x));

  // Teste un diviseur premier après l'autre
  do {
    // Tant que notre diviseur divise x, divise succéssivement x
    // par celui-ci en comptant le notre de divisions = l'exposant du
    // diviseur
    exposant = 0;
    while (x % DiviseurPremier == 0) {
      x /= DiviseurPremier;
      exposant++;
    }

    if (exposant) {
      // Rajoute le signe multiplier (si la chaîne n'est pas vide)
      if (NbrFacteur)
        printf ("*%ld",DiviseurPremier);
      else
        printf ("%ld",DiviseurPremier);

      // Un facteur de plus !
      NbrFacteur++;

      // Ecrit l'exposant (s'il est différent de 1)
      if (exposant!=1) printf ("^%ld",exposant);

      // Si x=1, reste plus rien à factoriser !
      if (x==1) {
        printf (" (%i facteurs premiers)\n",NbrFacteur);
        return;
      }
    }

    // Cherche le prochain nombre (diviseur) premier
    DiviseurPremier = ProchainPremier (DiviseurPremier+1);
  } while (DiviseurPremier<=RacineX);

  // x est un nombre premier ?
  if (x==SauveX) {
    printf ("%ld (nombre premier)\n",SauveX);
    return;
  }

  // Retourne la chaîne avec le dernier multiple
  printf ("*%ld (%i facteurs premiers)\n",x,NbrFacteur+1);
}
/******************************************************************************/
  //  Calcule le PGCD d'un nombre entier (PCGD = Plus Grand Commun Diviseur)
NombreZ Pgcd (NombreZ x, NombreZ y) {
  NombreZ pgcd;

  // Prend la valeur absolue des nombres
  x = Abs(x);
  y = Abs(y);

  // Pgcd(0,y) = y
  if (!x) return y;

  // Pgcd(x,0) = x
  if (!y) return x;

  // Calcule une première fois le reste de la division du premier par le
  // deuxième
  pgcd = x % y;
  while (pgcd) {
    // Maitenant X=Y et Y=Reste (=x % y)
    x = y;
    y = pgcd;

    // Calcule le reste de la division de X par Y
    pgcd = x % y;
  }

  // Finalement le Pgcd est Y (= dernier reste)
  return y;
}
/******************************************************************************/
  //  Calcule le PPCM d'un nombre entier (PPCM = Plus Petit Commun Multiple)
NombreZ Ppcm (NombreZ x, NombreZ y) {
  // Prend la valeur absolue de x et y
  x = Abs(x);
  y = Abs(y);

  // Le PPCM est en fait égal à X*Y/pgcd(x,y)
  return x*y/Pgcd(x,y);
}
/******************************************************************************/
  //  Calcule la somme des nombres entiers allant de "Debut" jusqu'à "Fin"
NombreZ Somme (NombreZ Debut, NombreZ Fin) {
  NombreZ Somme;
  NombreZ i;
  
  // Fin<Debut : Erreur !
  if (Fin<Debut) return 0;

  // Calcule la somme
  if (Debut==1) {
    // Somme(i,i,1,n) = n*(n+1)/2
    Somme = Fin-Debut+1;        // Calcule n
    Somme = Somme*(Somme+1)/2;  // Calcule n*(n+1)/2
  } else if (Debut==0) {
    // Somme(i,i,0,n) = n*(n+1)/2
    Somme = Fin-Debut;          // Calcule n
    Somme = Somme*(Somme+1)/2;  // Calcule n*(n+1)/2
  } else {
    Somme = 0;
    for (i=Debut; i<=Fin; i++) Somme += i;
  }

  // Renvoi la somme
  return Somme;
}

/******************************************************************************/
  // Calcule le produit des nombres entiers allant de "Debut" jusqu'à
  // "Fin". Remarque: Produit(x,y) = x!/y!
NombreZ Produit (NombreZ Debut, NombreZ Fin) {
  NombreZ Produit,i;

  // Fin<Debut : Erreur !
  if (Fin<Debut) return 0;

  // Calcule le produit
  Produit = Debut;
  for (i=Debut+1; i<=Fin; i++) Produit *= i;

  // Renvoi le produit
  return Produit;
}

/******************************************************************************/
  //  Calcule le factoriel d'un nombre entier
NombreZ Factoriel (NombreZ n) {
  NombreZ Produit,i;

  // Par convention : 0! = 1
  if (n==0) return 1;

  // Calcule le produit de (1*)2*3*...*n
  Produit = 1;
  for (i=2; i<=n; i++) Produit *= i;

  // Renvoi la somme
  return Produit;
}
/******************************************************************************/
  // Calcule NbrCombinaison(x,y) (nCr)
  // RQ: nCr (x,y) = x! / ((x-y)!*y!)
NombreZ NbrCombinaison (NombreZ x, NombreZ y) {
  // x<y : erreur !
  if (x<y) return 0;

  // y=1 ou x=y : ça vaut 1
  if ((y==1) || (x==y)) return 1;

  // nCr (x,y) = x! / [(x-y)!*y!] = ProduitEntier (x-y+1,x)/Factoriel(y)
  return Produit(x-y+1,x)/Factoriel(y);
}
/******************************************************************************/
  // Calcule NbrArrangement (x,y) (nPr)
  // RQ: nPr(x,y) = x!/(x-y)!
NombreZ NbrArrangement (NombreZ x, NombreZ y) {
  // x<y : erreur !
  if (x<y) return 0;

  // y=0 : (x-y)! = x!, donc nCr(x,y) = x!/x! = 1
  if (y==0) return 1;

  // nPr (x,y) = [x! / (x-y)!] = ProduitEntier (x-y+1,x)
  return Produit (x-y+1,x);
}
/******************************************************************************/
int main ()
{
  NombreZ i,n,p;

  // Efface l'écran
  clrscr();

  // Valeur absolue
  n = -37;
  printf ("Valeur absolue de %i = %i\n",n,Abs(n));

  // Affiche les nombres premiers de 1 à 50
  n = 20; p = 0;
  printf ("Nombres premiers de 1 à %i : ",n);
  for (i=0; i<=n; i++) if (EstPremier(i)) {
    if (p) printf (", ");
    printf ("%i",i);
    p++;
  }
  printf (" (%i nombres)\n",p);

  // Nombre premier suivant 5465
  n = 5465;
  printf ("Nombre premier suivant %i  : %i\n\n",n,ProchainPremier(n));
  
  // Factorise 4331787
  n = 4331787;
  printf ("Factorisation de %i = ",n); AfficheFactorisation (n);

  // Affiche le pgcd et le ppcm de 21 et 35
  n = 21; p = 35;
  printf ("\nPgcd(%i,%i) = %i",n,p,Pgcd(n,p));

  // Affiche le ppcm et le ppcm de 21 et 35
  n = 21; p = 35;
  printf (" et ppcm(%i,%i) = %i\n\n",n,p,Ppcm(n,p));

  // Somme des nombres de 1 à 10
  n = 1; p = 10;
  printf ("Somme des nombres de %i à %i = %i\n",n,p,Somme(n,p));

  // Produit des nombres de 3 à 7
  n = 3; p = 7;
  printf ("Produit des nombres de %i à %i = %i\n\n",n,p,Produit(n,p));

  // Nombre d'arrangement
  n = 8; p = 3;
  printf ("Nombre d'arrangements de (%i,%i) = %i (nPr)\n",n,p,NbrArrangement(n,p));

  // Produit des nombres de 3 à 7
  n = 5; p = 2;
  printf ("Nombre de combinaisons de (%i,%i) = %i (nCr)\n",n,p,NbrCombinaison(n,p));

  // Factoriel de 6 (6!)
  n = 6;
  printf ("%i! = %i\n\n",n,Factoriel(n));

  // Signature
  printf ("Un programme par Haypo - haypo@ifrance.com - http://www.haypocalc.com/\n\n");
}

Conclusion :


Venez sur http://www.haypocalc.com/ pour voir mes nouveaux programmes et avoir les dernières versions.

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.