Pgcd, ppcm, et factorisation de plusieurs nombres

Soyez le premier à donner votre avis sur cette source.

Vue 14 501 fois - Téléchargée 347 fois

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

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Messages postés
37
Date d'inscription
mardi 14 février 2006
Statut
Membre
Dernière intervention
4 mai 2010

Decimal, constructeur (UInt64)

Initialise une nouvelle instance de Decimal avec la valeur de l'entier non signé 64 bits spécifié.
C++

// Example of the Decimal( unsigned __int64 ) constructor.
using namespace System;

// Create a Decimal object and display its value.
void CreateDecimal( unsigned __int64 value, String^ valToStr )
{
Decimal decimalNum = Decimal(value);

// Format the constructor for display.
String^ ctor = String::Format( "Decimal( {0} )", valToStr );

// Display the constructor and its value.
Console::WriteLine( "{0,-33}{1,22}", ctor, decimalNum );
}

int main()
{
Console::WriteLine( "This example of the Decimal( unsigned "
"__int64 ) constructor \ngenerates the following output.\n" );
Console::WriteLine( "{0,-33}{1,22}", "Constructor", "Value" );
Console::WriteLine( "{0,-33}{1,22}", "-----------", "-----" );

// Construct Decimal objects from unsigned __int64 values.
CreateDecimal( UInt64::MinValue, "UInt64::MinValue" );
CreateDecimal( UInt64::MaxValue, "UInt64::MaxValue" );
CreateDecimal( Int64::MaxValue, "Int64::MaxValue" );
CreateDecimal( 999999999999999999, "999999999999999999" );
CreateDecimal( 0x2000000000000000, "0x2000000000000000" );
CreateDecimal( 0xE000000000000000, "0xE000000000000000" );
}

/*
This example of the Decimal( unsigned __int64 ) constructor
generates the following output.

Constructor Value
----------- -----
Decimal( UInt64::MinValue ) 0
Decimal( UInt64::MaxValue ) 18446744073709551615
Decimal( Int64::MaxValue ) 9223372036854775807
Decimal( 999999999999999999 ) 999999999999999999
Decimal( 0x2000000000000000 ) 2305843009213693952
Decimal( 0xE000000000000000 ) 16140901064495857664
*/
Messages postés
3011
Date d'inscription
jeudi 26 septembre 2002
Statut
Membre
Dernière intervention
27 novembre 2004
7
de rien ;)
tu a la classe de BlackGoddess pour aller plus loin

http://www.cppfrance.com/code.aspx?ID=10720
Messages postés
55
Date d'inscription
mardi 16 septembre 2003
Statut
Membre
Dernière intervention
4 août 2008

Voilà, la source a été mise à jour avec les __int64, merci beaucoup...

:-)
Messages postés
55
Date d'inscription
mardi 16 septembre 2003
Statut
Membre
Dernière intervention
4 août 2008

__int64, je l'ecris avec les deux __devant ? C'est quoi ces deux machins???
Je ne connaissais même pas, lol. Je suis vraiment nul en c++, va falloir que je lise des livres ou que je prennes des cours, pour m'y mettre sérieusement...

khayyam, ici, pour le unsigned machin, je ne pouvais pas l'utiliser car dans mon code, j'utilise justement le fait que lorsque la limite du machin est atteinte, alors ensuite on obtient un nombre négatif, ce qui n'est pas vrai avec des unsigned machin, vu que tous les nombres sont obligatoirement positifs...
J'ai bien vu qu'il y avait le header <limits.h>, avec les constantes MAX_INT, etc. mais je n'ai pas réussi à les utiliser dans un programme pour que ce soit fonctionnel.

Voilà tout, en vous remerciant pour vos commentaires, et encore une fois, merci djl, membre (toujours) très actif au sein de la communauté cppfrance.
Messages postés
51
Date d'inscription
lundi 7 juin 2004
Statut
Membre
Dernière intervention
15 juillet 2005

penser aussi au type unsigned machin pour doubler la plage de valeurs
Afficher les 6 commentaires

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.