C++中如何求最小公倍数 |holyya.com

C++中如何求最小公倍数

2023-07-05 00:53:27 深夜i -- --

C++ 最小公倍数算法循环函数

在数学中，最小公倍数是指能够被两个或以上的整数同时整除的最小正整数。在C++中，我们可以使用数学公式和算法来求得两个数的最小公倍数。

最小公倍数可以通过两个数的乘积除以它们的最大公因数得到，即：LCM(a,b) = (a*b)/GCD(a,b)。因此，我们需要先求得它们的最大公因数，然后再使用此公式来求得最小公倍数。

在C++中，我们可以使用递归或迭代的方式来实现求最大公因数的算法。其中，欧几里得算法也称为辗转相除法是一种经典的递归算法，它可以用来计算两个数的最大公因数。

欧几里得算法的基本思想是，将两个整数a和b做除法，计算商和余数，然后用余数递归地计算得到的两个数之间的最大公因数，直到某个数为0为止，此时另一个数就是最大公因数。

下面是使用欧几里得算法求最大公因数和最小公倍数的C++代码示例：


#include <iostream>
using namespace std;
int gcd(int a, int b)
{
  if(b == 0)
  
    return a;
  
  return gcd(b, a % b);
}
int lcm(int a, int b)
{
  return (a * b) / gcd(a, b);
}
int main()
{
  int a, b;
  cout << "Input two integers:" << endl;
  cin >> a >> b;
  cout << "GCD = " << gcd(a, b) << endl;
  cout << "LCM = " << lcm(a, b) << endl;
  return 0;
}

运行以上代码后，程序会要求输入两个整数，然后输出它们的最大公因数和最小公倍数。

在C++中求最小公倍数需要用到求最大公因数的算法，因此我们需要先掌握求最大公因数的方式，然后再使用上述公式来求得最小公倍数。当然，你也可以使用更高级的算法来计算最小公倍数，例如埃拉托色尼筛法、质因数分解等。

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

下一篇: C语言中的C++是什么？

评论区

()

相似文章