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