C++实现辗转相除法求最大公约数和最小公倍数 |21xrx.com

C++实现辗转相除法求最大公约数和最小公倍数

2023-07-11 04:42:37 深夜i -- --

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

辗转相除法是一种求两个数最大公约数和最小公倍数的经典算法，也是C++语言中常用的数学计算方法之一。其原理是通过反复进行两个数的除法运算，得到两个数的余数，直到余数为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) {
  int g = gcd(a, b);
  return a * b / g;
}
int main() {
  int a = 12;
  int b = 18;
  
  int g = gcd(a, b);
  int l = lcm(a, b);
  
  cout << "最大公约数：" << g << endl;
  cout << "最小公倍数：" << l << endl;
  
  return 0;
}

在上述代码中，我们定义了两个函数gcd和lcm，其中gcd函数用于求两个数的最大公约数，lcm函数用于求两个数的最小公倍数。在main函数中，我们通过调用gcd和lcm函数来计算a和b的最大公约数和最小公倍数，最后将计算结果输出到控制台中。

运行结果：

最大公约数：6 最小公倍数：36

从运行结果可以看出，我们成功地使用C++中的辗转相除法求出了a和b的最大公约数和最小公倍数。同时也说明了辗转相除法是一种简单有效的求解最大公约数和最小公倍数的算法，能够在实际问题中得到广泛应用。

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

下一篇: visual c++ 6.0不能正常运行，怎么办？

评论区

()

相似文章