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

Soyez le premier à donner votre avis sur cette source.

Snippet vu 9 373 fois - Téléchargée 36 fois

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

Ajouter un commentaire Commentaire
Messages postés
6
Date d'inscription
vendredi 11 janvier 2002
Statut
Membre
Dernière intervention
1 août 2002

Je suis content qu'on ai téléchargé mon code source plus de 200 fois !
Si vous voulez en savoir encore plus sur le calcul avec des nombres entiers, ou plus généralement sur les calculs appliqués en informatique, visitez mon site web :
http://www.haypocalc.com/

Il n'ai pas souvent mis à jour, mais quand c'est fait ça en vaut la peine!
@+ Haypo

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.