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.
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.