'LCM of two numbers

I am getting wrong result for my LCM program.

Ifirst find gcd of the numbers and then divide the product with 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;
}

Any help much appreciated.

calgorithmoverflowgreatest-common-divisorlcm


Solution 1:[1]

Problem 1) int gcd = gcd(x,y);

gcd is already defined to be a function. You cannot define a variable with the same name.

Problem 2) Change return y to return x in gcd() otherwise 0 will be returned everytime.

Problem 3) x * y may overflow if x and y are large.

Solution 2:[2]

You should return x instead of y in your gcd function.

Also, are you sure the product x*y will always fit into an int? Might be a good idea to use a long long for that as well.

Solution 3:[3]

#include <iostream>

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<<lcm(a,b)<<endl;
    return 0;
}

Solution 4:[4]

This C program is different approach towards finding LCM

 #include<stdio.h>
    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);
    }

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 Prasoon Saurav
Solution 2 MAK
Solution 3
Solution 4 Pious Alex

Related Questions