C++实现最小公倍数的算法 |21xrx.com

C++实现最小公倍数的算法

2023-07-10 21:25:27 深夜i 9 0

C++ 最小公倍数算法

最小公倍数（LCM）是数学中非常常见的一个概念，它指的是两个或多个数的公共倍数中最小的一个。在计算中，很多时候我们需要求出两个数的最小公倍数。那么，在C++中，我们可以如何实现最小公倍数的算法呢？

方法一：使用辗转相除法

辗转相除法是一种求最大公约数的常用算法。在使用这种算法求最小公倍数时，我们可以根据最大公约数来求解。具体操作如下：

1. 求出两个数的最大公约数。

2. 将两个数相乘，然后除以最大公约数即可求出最小公倍数。

使用C++代码实现如下：

#include<iostream>
using namespace std;
// 求最大公约数
int gcd(int a, int b)
{
  if (a % b == 0) return b;
  return gcd(b, a % b);
}
// 求最小公倍数
int lcm(int a, int b)
{
  return a * b / gcd(a, b);
}
int main()
{
  int a, b;
  cin >> a >> b;
  cout << lcm(a, b) << endl;
  return 0;
}

方法二：使用循环枚举法

循环枚举法是一种比较暴力的算法，如果两个数比较小的话，可以考虑使用这种方法。具体操作如下：

1. 首先比较两个数的大小，将较大的数存储到另外一个变量中，作为循环的上限。

2. 然后开始从较大数开始循环，每次循环都将其与原来的数相乘，然后再除以较小的数，如果能整除，则说明当前数是最小公倍数，退出循环即可。

使用C++代码实现如下：

#include<iostream>
using namespace std;
// 求最小公倍数
int lcm(int a, int b)
{
  int maxNum = max(a, b);
  int minNum = min(a, b);
  for (int i = maxNum; ; i++)
  {
    if (i % minNum == 0 && i % maxNum == 0) return i;
  }
}
int main()
{
  int a, b;
  cin >> a >> b;
  cout << lcm(a, b) << endl;
  return 0;
}

综上所述，C++中实现最小公倍数算法的方法有很多种，以上就是其中两种常见的方法。具体选择哪一种方法，可以根据实际情况进行判断。

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

下一篇: C++编程求解长方形面积

评论区

相似文章