两个数字的LCM

Question

我的LCM计划结果出错了.

如果找到数字的gcd,然后用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;
}

任何帮助非常感谢.

Answer 1

您的gcd功能将始终返回0.更改

return y;

至

return x;

理解Euclid的算法:

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

考虑x = 12和y = 18

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

你可以看到什么时候y变为零x将是gcd你需要返回x而不是y.

另外,在计算lcm时,您将首先乘以可能导致溢出的数字.相反,你可以这样做:

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

但如果lcm不能适应int你必须做到的long long