C++实现最大公约数和最小公倍数求解 |21xrx.com

2023-07-04 20:49:27 深夜i -- --

C++ 最大公约数最小公倍数求解

最大公约数和最小公倍数是数学中常见的一个概念，对于程序员来说，实现该函数对于解决某些问题来说也是很有帮助的。本文将着重介绍在C++中实现求解最大公约数和最小公倍数的方法。

一、最大公约数求解

最大公约数的定义是：两个数中同时能整除他们的最大正整数。在C++中可以使用递归实现最大公约数求解。代码如下：


int gcd(int x, int y){
  if(x == 0) return y;
  return gcd(y % x, x);
}

通过不断利用辗转相除法，求出两个数的余数，直到其中一个数为0时，另一个数就是最大公约数。

二、最小公倍数求解

最小公倍数的定义是：两个数的乘积除以最大公约数就是最小公倍数。因此，可以用一个公式求解最小公倍数，即lcm(x, y) = x * y / gcd(x, y)。将求解最大公约数的函数和这个公式结合起来，就可以得到求解最小公倍数的函数。代码如下：


int lcm(int x, int y){
  return x * y / gcd(x, y);
}

这段代码中，除了调用了求解最大公约数的函数，还用到了一个简单的公式来解决最小公倍数的问题。

最后，总结一下：在C++中实现最大公约数和最小公倍数求解，其实很简单，只需要利用辗转相除法和简单的公式即可。希望通过这篇文章，读者们可以更好地理解最大公约数和最小公倍数的概念，也能够更好地运用C++语言来实现这两个函数的求解。

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

下一篇: C++标准库包含多少个文件？

()

相似文章