21xrx.com
2024-11-22 03:00:09 Friday
登录
文章检索 我的文章 写文章
C++求最小公倍数的方法
2023-07-12 04:42:38 深夜i     --     --
C++ 最小公倍数 算法 循环 递归

最小公倍数(LCM)是指两个或多个数能够整除的最小正整数。在C++中,我们可以通过以下几种方法求得最小公倍数。

方法1:暴力枚举

我们可以通过枚举的方式找到两个数的最小公倍数。具体来说,我们可以从两个数中较大的数开始,依次加上它们的值,直到能够整除这两个数为止。

示例代码:

int lcm(int a, int b) {

  int max_num = max(a, b);

  int lcm = max_num;

  while (true) {

    if (lcm % a == 0 && lcm % b == 0)

      break;

    lcm += max_num;

  }

  return lcm;

}

方法2:欧几里得算法

欧几里得算法(又称辗转相除法)是求最大公约数的一种方法。同时,我们也可以利用它来求最小公倍数。它的基本原理是将较大数除以较小数,直到余数为0为止。最后一次的除数即为最大公约数。

示例代码:

int gcd(int a, int b) {

  return b == 0 ? a : gcd(b, a % b);

}

int lcm(int a, int b) {

  return a * b / gcd(a, b);

}

方法3:利用STL库函数

C++ STL库中提供了一个函数__gcd,在功能上与欧几里得算法相同,可以求出两个数的最大公约数。进一步地,我们可以通过以下代码求出两个数的最小公倍数,即a与b的积除以它们的最大公约数。

示例代码:

#include

int lcm(int a, int b) {

  return a * b / __gcd(a, b);

}

总结

以上是C++求最小公倍数的三种方法,它们都能够快速准确地求出最小公倍数。在使用时,可以根据实际情况选择合适的方法。同时,我们需要注意代码的清晰度和可读性,保持良好的编码风格。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复