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

C++实现求两个数的最小公倍数

2023-06-27 04:47:09 深夜i -- --

C++ 最小公倍数两个数

最小公倍数是指两个数中能同时整除的最小的正整数，也就是它们的公共倍数中最小的一个。在计算机编程中，我们经常需要求得两个数的最小公倍数。下面介绍常用的C++实现方法。

1. 辗转相除法

辗转相除法，也称为欧几里得算法，是求最大公约数的常用方法。最小公倍数是通过最大公约数推导得到的，因此也可以使用辗转相除法来求最小公倍数。

具体实现如下：


int gcd(int x, int y) {  // 辗转相除法求最大公约数
  if (y == 0) return x;
  return gcd(y, x % y);
}
int lcm(int x, int y) {  // 求两个数的最小公倍数
  return x * y / gcd(x, y);
}

在这段代码中，先用辗转相除法求出最大公约数，然后用两个数的乘积除以最大公约数即可得到最小公倍数。

2. 穷举法

穷举法又称为枚举法，它的思路是从两个数中较大的开始，依次尝试是否能整除两个数，能整除的第一个数即为它们的最小公倍数。

具体实现如下：


int lcm(int x, int y) {
  int max_num = max(x, y);
  while (true) {
    if (max_num % x == 0 && max_num % y == 0)
      return max_num;
    
    max_num++;
  }
}

这段代码从两个数中较大的数开始，每次增加1判断是否能被两个数整除，找到第一个能整除的数即为最小公倍数。

总结：

两种方法各有优缺点。辗转相除法可以通过迭代来实现，计算速度较快，但如果两个数非常大，可能会出现栈溢出的情况。穷举法虽然简单，但如果两个数非常大，需要枚举的数也会非常多，运算速度较慢。

因此，在实际应用中，可以根据数据的大小和情况选择合适的方法，也可以通过随机数方法来提高计算效率。

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

下一篇: C++和嵌入式：哪个更难？

评论区

()

相似文章