21xrx.com
2025-04-28 09:36:57 Monday
文章检索 我的文章 写文章
C++求解最大公约数的方法
2023-07-05 08:58:16 深夜i     19     0
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;
}

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

  
  

评论区

请求出错了