C++算法：求最大公约数和最小公倍数 |21xrx.com

2023-06-23 20:43:52 深夜i -- --

C++ 算法最大公约数最小公倍数

C++算法是计算机科学中常用的一种算法，它可以用来求解各种问题。在其中，求最大公约数和最小公倍数是一种非常常见的问题。下面我们来介绍一下C++算法如何求解最大公约数和最小公倍数。

最大公约数（GCD），即两个数的公共因数中最大的那个数。C++中可以使用辗转相除法来求解两个数的最大公约数，其代码实现如下：


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

其中，a和b是要求解的两个数，r表示取模余数，while循环的条件为b不等于0。在每次循环中，先求a除以b的余数r，再将b赋值为r，将a赋值为原来的b，直至b为0，最终a就是这两个数的最大公约数。

最小公倍数（LCM）是在两个正整数均为不为0时，两个数的乘积除以它们的最大公约数。C++中可以使用最大公约数来求解两个数的最小公倍数，其代码实现如下：


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

在代码中，使用gcd(a,b)求出a和b的最大公约数，然后用a * b除以最大公约数，即为最小公倍数。

以上就是C++算法求解最大公约数和最小公倍数的实现方法。C++算法简单高效，我们可以将它用于各种项目中。

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

下一篇: C++编写手机应用程序

()

相似文章