C++求两个正整数的最大公约数和最小公倍数 |21xrx.com

2023-07-11 16:20:10 深夜i 45 0

C++ 正整数最大公约数最小公倍数

在计算机科学中，最大公约数和最小公倍数是两个正整数的重要概念。最大公约数指的是两个数共有的约数中最大的那一个，而最小公倍数指的是两个数的公倍数中最小的那一个。在C++编程中，有多种方法可以求解两个正整数的最大公约数和最小公倍数。

最大公约数：

一种求解最大公约数的方法是使用辗转相减法，具体实现为：

int gcd(int a, int b) {
  while (a != b) {
    if (a > b)
      a -= b;
     else
      b -= a;
    
  }
  return a;
}

上述代码中，使用while循环不断将两个数中较大的数减去较小的数，直到两个数相等为止。此时的数即为最大公约数。该方法的时间复杂度为O(max(a,b))，是一个比较简单但比较低效的算法。

另外一种求解最大公约数的方法是使用辗转相除法，具体实现为：

int gcd(int a, int b) {
  int temp;
  while (b != 0)
    temp = a % b;
    a = b;
    b = temp;
  
  return a;
}

该方法的时间复杂度为O(log(max(a,b)))，比较高效。

最小公倍数：

求解最小公倍数的方法是将两个数相乘后除以它们的最大公约数，具体实现为：

int lcm(int a, int b) {
  int temp = gcd(a, b);
  return (a * b) / temp;
}

通过调用前面实现的最大公约数方法，求得两个数的最大公约数，然后用a、b的乘积除以最大公约数即可得到它们的最小公倍数。

除了使用上述方法，还可以使用更高效的算法求解最大公约数和最小公倍数，如较大数不断与较小数的余数相除，或使用更高级的算法，如扩展欧几里得算法等。

总之，在C++编程中，求解两个正整数的最大公约数和最小公倍数是非常基本和常见的问题，需要掌握至少一种求解方法，以便于解决与它们相关的问题。

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

下一篇: 如何在C++中定义全局变量数组？

相似文章