C++如何求公倍数？ |21xrx.com

C++如何求公倍数？

2023-07-06 13:34:06 深夜i -- --

C++ 公倍数求解

在编程中，计算公倍数是一个经常出现的问题。而在C++中，求公倍数的方法有很多种，这里我们介绍两种方法。

方法1：暴力枚举法

暴力枚举法是一种直接的、容易理解的计算公倍数的方法。它的基本思路是先取两个数中较大的那个数，然后依次判断这个数乘以1、2、3、4...等是否能被另一个数整除。如果能，那么这个数就是两个数的公倍数。具体实现代码如下：


#include <iostream>
using namespace std;
int main()
{
  int a, b, max;
  cout << "请输入两个正整数: ";
  cin >> a >> b;
  max = (a > b) ? a : b; // 取两个数中较大的数
  while(true)
  {
    if(max % a == 0 && max % b == 0)
    
      cout << "最小公倍数是" << max << endl;
      break;
    
    max++;
  }
  return 0;
}

上面这段代码中，我们用 while 循环枚举从较大的数开始逐个判断是否为其公倍数，当找到第一个同时能被两个数整除的数时，即为这两个数的最小公倍数。该方法的缺点是效率较低，当两个数的乘积较大时，需要枚举的数也会很多，程序运行时间会很长。

方法2：辗转相除法

辗转相除法又叫欧几里得算法，它用递归的方式求两个数的最大公约数，然后利用最大公约数求最小公倍数。其基本思路是利用两个数的最大公约数与最小公倍数的关系来求解。具体实现步骤如下：

1. 计算 a 和 b 的最大公约数 d。

2. 最小公倍数 L = a * b / d。

用代码来实现，可以写成这样：


#include <iostream>
using namespace std;
// 求两个数的最大公约数
int gcd(int a, int b) {
  return b == 0 ? a : gcd(b, a % b);
}
int main()
{
  int a, b;
  cout << "请输入两个正整数: ";
  cin >> a >> b;
  int d = gcd(a, b); // 计算最大公约数
  int L = a * b / d; // 求最小公倍数
  cout << "最小公倍数是" << L << endl;
  return 0;
}

辗转相除法是一种较为高效的求最小公倍数的方法，不仅占用内存小，而且计算速度快。

以上就是两种在C++中求公倍数的方法。在实际编程中，我们可以选择适合自己的方法来求解，以达到更高的效率和更好的实现。

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

下一篇: "C++ Builder的TEdit：如何提高代码的合理性"

评论区

()

相似文章