如何在C++中求最大公约数和最小公倍数 |21xrx.com

2023-07-08 04:39:54 深夜i -- --

C++ 最大公约数最小公倍数算法辗转相除法

在C++中，求两个数的最大公约数和最小公倍数是常见的问题。这篇文章将介绍两种常用的解决方法。

求最大公约数

辗转相除法是一种简单有效的求最大公约数的方法。其基本原理是用较大的数除以较小的数，得到余数，然后用较小的数除以余数，再得到余数，直到余数为0为止，此时较小的数就是最大公约数。

下面是用C++代码实现辗转相除法：


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

该函数接受两个整数a和b作为参数，并返回它们的最大公约数。在while循环中，我们不断计算a和b的余数，并将a和b交换，直到b为0为止。此时a的值就是最大公约数。

求最小公倍数

求最小公倍数的方法有很多，其中一个常用的方法是先求最大公约数，然后用两个数的乘积除以最大公约数。

下面是用C++代码实现这种方法：


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

该函数接受两个整数a和b作为参数，并返回它们的最小公倍数。在函数中，我们先调用上面写的gcd函数求出a和b的最大公约数g，然后将a和b的乘积除以g即可得到最小公倍数。

总结

求最大公约数和最小公倍数是经常出现的问题，我们可以用辗转相除法或先求最大公约数再求最小公倍数的方法来解决。在编写代码时，需要注意整数值的范围，以免溢出。

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

下一篇: Node.js模块移植

()

相似文章