C++如何求最小公倍数 |21xrx.com

2023-06-30 11:54:46 深夜i -- --

C++ 最小公倍数求解

最小公倍数（LCM）指的是两个或多个数的公共倍数中最小的那个。在C++里使用递归和辗转相除法来求解最小公倍数。

首先，我们需要定义一个函数来求最大公约数（GCD）：


int GCD(int a, int b) {
 if (b == 0)
  return a;
  else {
  return GCD(b, a % b);
 }
}

接着，我们可以使用最大公约数来求得最小公倍数：


int LCM(int a, int b) {
 return (a * b) / GCD(a, b);
}

这个函数使用了公式：两个数的积等于它们的最大公约数和最小公倍数的积。因此，只需要调用GCD函数来求得最大公约数，然后乘以两个数的积再除以最大公约数，就可以得到它们的最小公倍数了。

但这种方法只适用于两个数的情况。对于多个数的情况，我们可以使用递归来处理。具体的，我们可以把前两个数求得的最小公倍数再和下一个数求最小公倍数，以此类推，一直到处理完所有的数。下面是代码实现：


int LCM(int arr[], int n) {
 if (n == 1) {
  return arr[0];
 } else {
  return LCM(arr[0], LCM(&arr[1], n - 1));
 }
}

这个函数将数组的第一个元素和剩余的元素一起递归调用自己，直到数组中只剩下一个元素。如果数组中只有一个元素，则返回该元素作为最小公倍数。

总之，C++里可以使用递归和辗转相除法来求得最小公倍数。对于两个数的情况，我们可以直接套用公式；对于多个数的情况，我们可以使用递归来处理。

上一篇: idea打包java可执行jar包

下一篇: C++不支持中文输入

()

相似文章