求解两个整数的C++最小公倍数 |21xrx.com

求解两个整数的C++最小公倍数

2023-06-30 17:27:26 深夜i 13 0

C++ 最小公倍数整数

最小公倍数是指两个或多个整数之间的最小倍数，在数学上非常常见。如果你正在学习C++编程语言，很有可能会需要求解两个整数的最小公倍数。本文将提供几种方法来实现这一目标。

方法一：暴力解法

这种方法较为简单，但不是最优解。其基本思路是：首先找到两个整数中较大的那个数，然后从该数开始不断加倍数，直到找到一个数是两个整数的公倍数。

下面是对应的C++代码：

int lcm(int a, int b) {
  int i = max(a, b);
  while(i % a || i % b) i++;
  return i;
}

该函数的时间复杂度为O(max(a,b))。

方法二：辗转相除法

辗转相除法是求两个数的最大公约数的常用方法。通过不断求解最大公约数，最终即可得出最小公倍数。

具体来说，算法的主要步骤如下所示：

1. 求两个数的最大公约数，即gcd(a,b)。

2. 用两个数的乘积除以其最大公约数，即a*b/gcd(a,b)，即为最小公倍数。

下面是对应的C++代码：

int gcd(int a, int b) {
  return b == 0 ? a : gcd(b, a % b);
}
int lcm(int a, int b) {
  return a / gcd(a, b) * b;
}

该算法的时间复杂度为O(log max(a,b))。

方法三：枚举因子法

该方法的基本思路是，枚举两个数的所有因子，找到它们的公共因子，然后再将这些公共因子相乘即为最小公倍数。

具体来说，算法的主要步骤如下所示：

1. 枚举两个数的因子。

2. 找到这两个数的公共因子。

3. 将这些公共因子相乘即为最小公倍数。

下面是对应的C++代码：

int factor(int a, int b) {
  int f = 1;
  for(int i = 2; i <= min(a, b); i++) {
    if(a % i == 0 && b % i == 0) {
      a /= i; b /= i;
      f *= i;
      i--;
    }
  }
  return f * a * b;
}
int lcm(int a, int b) {
  return factor(a,b);
}

该算法的时间复杂度为O(min(a,b))。

综上所述，以上这三种方法均可以用来求解两个整数的最小公倍数。对于小规模数据，我们可以使用暴力算法。对于中等规模的数据，我们可使用辗转相除法。而对于大规模数据，则建议使用枚举因子法，该方法运行速度较快，且复杂度不高，是最优解的一个重要方法。

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

下一篇: Nodejs编写的自动化测试工具是什么？

评论区

相似文章