PGCD, PPCM, ET FACTORISATION DE PLUSIEURS NOMBRES

#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++;
   }
}