Pgcd, ppcm, et factorisation de plusieurs nombres

Télécharger le projet
Commenter

Description

Ce code permet de factoriser plusieurs nombres en produit de facteurs premiers, de calculer le pgcd de deux nombres par l'algorithme d'Euclide, le ppcm de deux nombres, à partir du pgcd de ces deux nombres, et de généraliser au pgcd et ppcm d'une série de nombres, en calculant pgcd et ppcm de proche en proche...
(voir le commentaire en dessous du code pour les limitations des grands nombres, pour lesquels le programme ne sait pas calculer le ppcm).

Source / Exemple : 


#include <iostream.h>
#include <stdlib.h>
#include <conio.h>

int facteurs[150][50];  //on peut mettre un maximum de 150 nbres, qui valent au moins 2^50 (très supérieur à la limitation imposée par les int)
void initialisation(void); //initialisation du tableau facteurs[150][50] à -1
int pgcd(int, int);  //pgcd de deux nombres par l'algorithme d'Euclide
__int64 ppcm(__int64, int);  //ppcm de deux nombres, à partir du pgcd de ces deux nombres
void factorisation (int, int); //remplissage du tableau de facteurs premiers pour chaque nombre
void affichage(int *, int); //affichage du tableau de decomposition en produit de facteurs premiers

int main(void)
{
bool erreur = false;  //savoir si les limites des __int64 sont atteintes (18 446 744 073 709 551 616 ???)
int x=0;  //combien de nbres vous souhaitez factoriser, etc.
int nbre[150]={-1};  //le maximum est 150 nbres...
int pgcdtemp;  //nbre temporaire et résultat pour pgcd
__int64 ppcmtemp;  //nbre temporaire et résultat pour ppcm de type __int64 pour les grands nombres

initialisation(); //on initialise le tableau des facteurs premiers à -1

while (x<2)
	{
	cout<<"Combien souhaitez vous entrer de nombres (minimum = 2) ?\n";
	cout<<"Votre reponse : ";
	cin>>x;
	}

for (int i=0;i<x;i++)
	{
   cout<<"Nombre "<<(i+1)<<" = ";
   cin>>nbre[i];
   while (nbre[i]<0) {cout<<"Entrez un nombre positif!, retapez le nombre "<<i<<" : "; cin>>nbre[i];}
   }

clrscr();
cout<<"\n";

for (int i=0;i<x;i++)
{
factorisation(nbre[i],i);  //remplissage du tableau des facteurs premiers
affichage(&nbre[i],i);     //affichage de tous les facteurs premiers pour chaque nombre
}

pgcdtemp=nbre[0];   //on entre le premier de la liste
ppcmtemp=nbre[0];   //dans une variable temporaire (de type __int64 pour ppcmtemp)

cout<<"\n\n";

for (int i=0;i<(x-1);i++)    //calcul du pgcd de proche en proche d'apres tous vos nombres entrés
	{
   pgcdtemp=pgcd(pgcdtemp,nbre[i+1]);
   }

for (int i=0;i<(x-1);i++)   //calcul du ppcm de proche en proche d'apres tous vos nombres entrés
	{
   ppcmtemp=ppcm(ppcmtemp,nbre[i+1]);
   if (ppcmtemp==-1) {erreur=true;}
   }

//affichage du resultat du pgcd de tous les nombres entrés
cout<<"PGCD (";
for (int i=0;i<(x-1);i++) cout<<nbre[i]<<",";
cout<<nbre[x-1]<<") = "<<pgcdtemp;
if (pgcdtemp==1) cout<<"  --> tous ces nombres sont premiers entre eux."<<endl;
else cout<<endl;

cout<<"\n";

//affichage du resultat du ppcm de tous les nombres entrés
if (erreur==false)  //si erreur=true, alors on est au dessus de la limite imposée par les __int64 (2 puissance 64), donc on écrit que l'ordinateur ne peut pas le calculer
	{
cout<<"PPCM (";
for (int i=0;i<(x-1);i++) cout<<nbre[i]<<",";
cout<<nbre[x-1]<<") = "<<ppcmtemp<<endl;
	}
else
	{
cout<<"PPCM (";
for (int i=0;i<(x-1);i++) cout<<nbre[i]<<",";
cout<<nbre[x-1]<<") = nombre trop grand,\n";
cout<<"\t\tl'ordinateur ne peut pas le calculer\n";
	}

cout<<"\n\n\n";

system("pause");
return 0;
}  //fin du main()

void initialisation(void)
{
for (int j=0;j<150;j++)
	{
   for (int i=0;i<50;i++) {facteurs[j][i]=(-1);}
   }
}

int pgcd(int a, int b)  //algorithme d'Euclide
{
int c=-1;
while (c!=0)
	{
   c=a%b;
   a=b;
   if (c!=0) b=c;
   }
return b;
}

void factorisation(int n, int m)   //on calcul la decomposition en facteurs premiers du nombre selectionné
{
int test=n;
int i=0;
int facteur=2;
while (test!=1)
{
if ((test%facteur)==0)
	{
   facteurs[m][i]=facteur;
   i++;
   test/=facteur;
   facteur=2;
   }
else {facteur++;}
}
}

__int64 ppcm(__int64 a, int b)
{
int c=pgcd(a,b);
if ((a * (__int64) b)<=0) return -1; //si le resultat de a*b est inférieur à zéro, alors on a atteind la limite des __int64 (2 puissance 64), on ne peut donc plus calculer le ppcm, on retourne -1 (erreur=true)
else return ((a*(__int64) b)/((__int64) c));
}

void affichage(int *n, int a) //affichage, par exemple: 25 = 5 * 5
{
int i=0;
cout<<*n<<" = ";
while (facteurs[a][i]!=(-1))
	{
   if (facteurs[a][i+1]!=(-1)) {cout<<facteurs[a][i]<<" x ";}
   else {if (i==0) {cout<<facteurs[a][i]<<" --> Ce nombre est premier...\n\n";} else {cout<<facteurs[a][i]<<"\n\n";}}
   i++;
   }
}

Conclusion :


Je souhaiterais pouvoir calculer le ppcm pour plus de nombres, et/ou des nombres plus grands, mais le ppcm devient très rapidement énorme (plusieurs dixaines de chiffres).
Donc je suis limité par les limites des int par exemple, ou des long doubles, etc...

Je ne sais pas comment faire pour dépasser ces limites qui sont relativement "faibles", par exemple 2 147 483 647 pour les int signés.
Donc le programme ne permet pas de calculer des ppcm supérieurs à cette limitation imposée par le type utilisé.
Si quelqu'un peut me donner une réponse, je lui serais très reconnaissant.

PS: J'ai bien vu qu'il existe des classes pour manipuler les nombres très grands, mais je trouve ça relativement compliqué, car je voulais en programmer une il y a peu de temps en m'aidant des sources présentes, mais je n'ai pas réussi!!!
bouh, la honte, lol.

Mise à jour : Grace à djl, je suis passé aux limitations des __int64, ce qui est déjà beaucoup plus intéressant pour moi, mais je souhaiterais aller encore plus loin, si quelqu'un peut m'aider...???
Télécharger le projet

Codes Sources

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.

Du même auteur (cs_jb60)