21xrx.com
2025-06-19 15:37:01 Thursday
文章检索 我的文章 写文章
C++解题思路：最大公约数和最小公倍数
2023-06-23 01:22:49 深夜i     25     0
C++ 最大公约数 最小公倍数 解题思路 编程技巧

在编程中，经常需要求两个数的最大公约数和最小公倍数。在C++中，我们可以使用欧几里得算法和辗转相除法来解决这个问题。

欧几里得算法又称辗转相除法，是求两个数最大公约数的一种算法。具体的实现方法是将较大的数除以较小的数，得到余数，再用较小的数去除余数，得到新的余数，直到余数为零为止。此时，较小的数即为最大公约数。

下面是一个使用欧几里得算法求最大公约数的示例代码：

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

最小公倍数的求解方法可以利用最大公约数求解。最小公倍数等于两个数之积除以它们的最大公约数。下面是一个使用最大公约数求解最小公倍数的示例代码：

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

除了欧几里得算法外，辗转相除法也可以用来求解最大公约数。辗转相除法的基本思想是将较大的数除以较小的数得到余数，然后把较小的数作为第一个数，余数作为第二个数进行新的除法运算，继续上述操作，直到余数为零。此时，较小的数就是最大公约数。

下面是一个使用辗转相除法求最大公约数的示例代码：

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

无论使用哪一种方法，求解最大公约数和最小公倍数都是非常基本的算法，常常出现在编程的各个领域中。我们需要灵活掌握这两种算法，并在实际编程过程中加以运用。

  
  

评论区