LCM de deux nombres

Je me trompe de résultat pour mon programme LCM.

D’abord, trouvez gcd des nombres puis divisez le produit avec gcd.

int gcd(int x, int y) { while(y != 0) { int save = y; y = x % y; x = save; } return y; } int lcm(int x, int y) { int prod = x * y; int Gcd = gcd(x,y); int lcm = prod / Gcd; return lcm; } 

Toute aide très appréciée.

Votre fonction gcd retournera toujours 0 . Changement

 return y; 

à

 return x; 

Comprendre l’algorithme d’Euclid:

 RULE 1: gcd(x,0) = x RULE 2: gcd(x,y) = gcd(y,x % y) 

considérer x = 12 et y = 18

  gcd (12, 18) = gcd (18, 12) Using rule 2 = gcd (12,6) Using rule 2 = gcd (6, 0) Using rule 1 = 6 

Comme vous pouvez le voir lorsque y devient zéro, x sera le gcd , vous devez donc renvoyer x et non y .

Aussi, en calculant lcm, vous multipliez d’abord les nombres, ce qui peut provoquer un débordement. Au lieu de cela, vous pouvez faire:

 lcm = x * (y / gcd(x,y)) 

mais si lcm ne peut pas tenir dans un int vous devrez le faire long long

Problème 1) int gcd = gcd(x,y);

gcd est déjà défini comme une fonction. Vous ne pouvez pas définir une variable du même nom.

Problème 2) Modifiez return y pour return x dans gcd() sinon 0 sera renvoyé à chaque fois.

Problème 3) x * y peut déborder si x et y sont grands.

Vous devriez retourner x au lieu de y dans votre fonction gcd.

De plus, êtes-vous sûr que le produit x * y ira toujours dans un int ? Peut-être une bonne idée d’utiliser une long long pour cela aussi.

 #include  using namespace std; long long gcd(long long int a, long long int b){ if(b==0) return a; return gcd(b,a%b); } long long lcm(long long a,long long b){ if(a>b) return (a/gcd(a,b))*b; else return (b/gcd(a,b))*a; } int main(){ long long int a ,b ; cin>>a>>b; cout< 

Ce programme C est une approche différente pour trouver LCM

  #include int main() { int a,b,lcm=1,i=2; printf("Enter two numbers to find LCM\n" ); scanf("%d %d",&a ,&b); while(i <= a*b) { if(a%i==0 & b%i==0) { lcm=lcm*i; a=a/i; b=b/i; i=i-1; } if( a%i==0 & b%i!=0) { lcm=lcm*i; a=a/i; i=i-1; } if( b%i==0 & a%i!=0) { lcm=lcm*i; b=b/i; i=i-1; } i++; } printf("The LCM of numbers is %d\n", lcm); }