calgorithmoverflowgreatest-common-divisorlcm

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.

Solution

  • Your gcd function will always return 0. Change

    return y;

    to

    return x;

    Understand the Euclid's algorithm:

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

    consider x = 12 and y = 18

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

    As you can see when y becomes zero x will be the gcd so you need to return x and not y.

    Also while calculating lcm you are multiplying the numbers first which can cause overflow. Instead you can do:

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

    but if lcm cannot fit in an int you'll have to make it long long