C++求解最大公约数的方法 |21xrx.com

C++求解最大公约数的方法

2023-07-05 08:58:16 深夜i -- --

C++ 求解最大公约数方法

在C++中，求解两个数的最大公约数可以使用辗转相除法和辗转相减法两种方法。下面我们分别介绍这两种方法的实现方式。

一、辗转相除法

辗转相除法（又称欧几里得算法）是一种通过逐步将较大的数除以较小的数所得的余数作为新的除数，余数为0时停止计算，最后得到的除数就是原来两个数的最大公约数的方法。

代码实现如下：


#include <iostream>
using namespace std;
int gcd(int a, int b)
{
  if (a < b)
    swap(a, b);
  while (b != 0)
  
    int r = a % b;
    a = b;
    b = r;
  
  return a;
}
int main()
{
  int a = 24;
  int b = 60;
  int result = gcd(a, b);
  cout << "最大公约数为：" << result << endl;
  return 0;
}

二、辗转相减法

辗转相减法是一种通过逐步将较大的数减去较小的数所得的差作为新的被减数，差为0时停止计算，最后得到的被减数就是原来两个数的最大公约数的方法。但是这种方法效率较低，因为每次计算都需要做减法运算。

代码实现如下：


#include <iostream>
using namespace std;
int gcd(int a, int b)
{
  if (a < b)
    swap(a, b);
  while (a != b)
  {
    int c = a - b;
    if (c < b)
      swap(c, b);
    a = c;
  }
  return a;
}
int main()
{
  int a = 24;
  int b = 60;
  int result = gcd(a, b);
  cout << "最大公约数为：" << result << endl;
  return 0;
}

综上所述，辗转相除法是求解最大公约数的一种比较高效的方法，应该优先选择使用。

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

下一篇: C++函数实现字符串比较：比较两个字符串的大小

评论区

()

相似文章