C++如何计算两个数的最小公倍数？ |21xrx.com

C++如何计算两个数的最小公倍数？

2023-07-05 07:51:19 深夜i 90 0

C++ 计算两个数最小公倍数

在数学中，最小公倍数是指两个或多个整数的公共倍数中最小的那一个。在C++中，计算两个数的最小公倍数可以通过使用循环、递归或欧几里得算法来实现。下面将介绍三种方法。

一、循环：

使用for循环可以找到两个数的所有公倍数，再找到其中最小值即可。具体实现如下：

// 循环方法计算两个数的最小公倍数
int lcm(int a, int b) {
  int max = (a > b) ? a : b;
  for (int i = max; ; i += max) {
    if (i % a == 0 && i % b == 0)
      return i;
    
  }
}

该方法的时间复杂度为O(max(a, b))，不适合计算较大的数的最小公倍数。

二、递归：

可以使用递归方法来计算两个数的最小公倍数。首先计算它们的最大公约数，然后用它们的积除以最大公约数即可得到最小公倍数。具体实现如下：

// 递归方法计算最大公约数
int gcd(int a, int b) {
  if (b == 0)
    return a;
  
  return gcd(b, a % b);
}
// 递归方法计算两个数的最小公倍数
int lcm(int a, int b) {
  return (a * b) / gcd(a, b);
}

该方法的时间复杂度为O(log(max(a, b)))，适合计算较大的数的最小公倍数。

三、欧几里得算法（辗转相除法）：

欧几里得算法是一种计算最大公约数的算法，可以通过它来计算最小公倍数。具体实现如下：

// 欧几里得算法计算最大公约数
int gcd(int a, int b) {
  if (b == 0)
    return a;
  
  return gcd(b, a % b);
}
// 欧几里得算法计算两个数的最小公倍数
int lcm(int a, int b) {
  return (a * b) / gcd(a, b);
}

该方法的时间复杂度也为O(log(max(a, b)))，适合计算较大的数的最小公倍数。

在实际应用中，可以根据数据大小和计算效率选择不同的方法来计算两个数的最小公倍数。

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

下一篇: 《数据结构与算法分析C++版第四版》

评论区

相似文章