C++如何求最大公因数 |21xrx.com

2023-06-24 00:12:30 深夜i 44 0

C++ 最大公因数算法

最大公因数是指两个或多个数共有的约数中最大的一个。在C++中，求最大公因数可以通过循环、递归或数学方法来实现。

1. 循环实现

使用while循环逐个枚举两个数的约数，找到它们的最大公因数。

int gcd(int a, int b) {
  int m = min(a, b);
  while (m > 0) {
    if (a % m == 0 && b % m == 0)
      return m;
    m--;
  }
  return 1;
}

2. 递归实现

使用递归调用函数，以辗转相除法求解两个数的最大公因数。

int gcd(int a, int b) {
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}

3. 数学方法实现

利用欧几里得算法，以精简的方式求解两个数的最大公因数。

int gcd(int a, int b) {
  while (b != 0)
    int t = a % b;
    a = b;
    b = t;
  
  return a;
}

以上是三种常见的C++求解最大公因数的方法。通过选择不同的方法，我们可以在实际应用中根据实际情况去编写相应的程序。

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

下一篇: C++ 程序中可以有几个主函数？

相似文章