两个数字的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;

理解欧几里德算法：

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

Answer 2

问题1) int gcd = gcd(x,y);

gcd已定义为函数。不能定义同名的变量。

问题2)在gcd()中将return y改为return x，否则每次返回0。

问题3)如果x和y很大，x * y可能会溢出。

Answer 3

您应该在gcd函数中返回x而不是y。

另外，您确定产品x*y将始终适合int吗？使用long long可能也是个好主意。