C++代码实现求两个数最大公约数和最小公倍数 |21xrx.com

2023-07-05 08:22:30 深夜i -- --

C++ 最大公约数最小公倍数代码实现

在数学中，两个非零整数的最大公约数是两个数中最大的公约数。而最小公倍数是能够被这两个数整除的最小正整数。

C++中有多种方法可以计算两个数的最大公约数和最小公倍数。下面我们将介绍两种常见的方法来实现这两个功能，供大家参考。

1. 辗转相减法

首先介绍计算最大公约数的方法——辗转相减法。该方法的基本思路是不断进行两个数的相减操作，直到两个数相等。这个相等的数就是它们的最大公约数。

下面是辗转相减法的C++代码：


int gcd(int a, int b)
{
  while(a != b)
  {
    if(a > b)
      a = a - b;
    else
      b = b - a;
  }
  return a;
}

这个代码中，我们通过连续相减的操作，不断地缩小a和b的值，再在它们相等时停止计算，返回a即可。

2. 辗转相除法

接下来介绍计算最小公倍数的方法——辗转相除法。该方法和辗转相减法类似，我们用一个循环不断进行除法操作，直到两个数能够同时被除尽，得到的值就是它们的最小公倍数。

下面是辗转相除法的C++代码：


int lcm(int a, int b)
{
  int t = gcd(a, b); //先求出最大公约数
  return a / t * b;  //计算最小公倍数
}

这个代码中，我们先利用前面所说的辗转相减法来计算最大公约数t，然后使用公式a * b / t来计算最小公倍数。

综上所述，我们通过辗转相减法和辗转相除法两种方法实现了求两个数的最大公约数和最小公倍数的功能。在实际编程中，我们可以根据自己的需要来选择使用其中的一种。

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

下一篇: C++如何统计字符串出现的次数

()

相似文章