C++中如何求解最小公倍数的算法 |21xrx.com

C++中如何求解最小公倍数的算法

2023-07-08 09:56:22 深夜i -- --

C++ 最小公倍数算法

在C++中，求解最小公倍数的算法主要有两种方法：辗转相减法和对于质因数分解法。

首先来看辗转相减法。该方法是通过将两个数中较大的数减去较小的数，进行连续的相减，直到两个数相等为止，此时的两个数就是原来两个数的最大公约数，而最小公倍数则可以通过原来两个数的乘积除以它们的最大公约数得到。代码实现如下：


int gcd(int a, int b) { //辗转相减法求最大公约数
  if (a == 0 || b == 0)
    return a + b;
  while (a != b) {
    if (a > b)
      a = a - b;
    else
      b = b - a;
  }
  return a;
}
int lcm(int a, int b) { //最小公倍数
  return a * b / gcd(a, b);
}

接下来是基于质因数分解的方法。该方法的基本思想是将两个数分别分解为若干个质因数的乘积，找到它们共同的质因数，并将共同的质因数相乘即可得到最小公倍数。代码实现如下：


int lcm(int a, int b) { //最小公倍数（基于质因数分解）
  int num1 = a, num2 = b;
  for (int i = 2; i <= a; i++) {
    while (num1 % i == 0 && num2 % i == 0)
      num1 /= i;
      num2 /= i;
      a /= i;
      b /= i;
    
  }
  return a * b * num1 * num2;
}

无论使用哪种方法，求解最小公倍数的时间复杂度都是O(log n)，因此在实际应用中，我们可以根据实际情况选择不同的算法，以便更加高效地求解最小公倍数。

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

下一篇: "C++编程：探究好玩有趣的代码"

评论区

()

相似文章