最高公因数或最大公约数是能够在不产生任何余数的情况下，能够同时整除两个或多个值的因数。在本文中，我们将讨论在C++中执行两个数字的HCF / GCD的几种方法。

这只是一个数学解决方案，有几种算法可以找到最大公约数。欧几里得方法是常见的找到最大公约数的方法。我们将在迭代模式和递归模式下使用相同的算法。

使用迭代方法

欧几里德求最大公约数的迭代解法在算法部分中展示。

算法

• 将两个数a和b作为输入。
• 如果a等于0，则返回b。
• 如果 b 为 0，则返回 a。
• 当a和b不相同时，执行操作。
  • 如果 a > b，则 a := a – b。
  • 否则 b := b - a。
• 结束循环。
• 将最大公因数作为变量 a 返回。

示例

#include <iostream>
using namespace std;

int solve( int x, int y) {
   if (x == 0)
      return y;
   else if (y == 0)
      return x;
   while (x != y) {
      if (x > y)
         x = x - y;
      else
         y = y - x;
   }
   return x;
}

int main( int argc, char* argv[] ) {
   cout << "HCF of two numbers 12 and 72 is: " << solve(12, 72) << endl;
   cout << "HCF of two numbers 18 and 13 is: " << solve(18, 13) <<   endl;
   cout << "HCF of two numbers 117 and 96 is: " << solve(117, 96) << endl;
   cout << "HCF of two numbers 85 and 15 is: " << solve(85, 15) << endl;
}

输出

HCF of two numbers 12 and 72 is: 12
HCF of two numbers 18 and 13 is: 1
HCF of two numbers 117 and 96 is: 3
HCF of two numbers 85 and 15 is: 5

使用迭代方法

可以使用递归方法来实现相同的欧几里得方法。下面我们将描述递归方法的定义，如下所示的算法。

算法

• 定义一个名为HCF的函数，该函数接受两个数字a和b。
• 如果a为0，则返回b
• 否则返回 HCF( b mod a, a)

示例

#include <iostream>
using namespace std;

int solve( int x, int y) {
   if (x == 0)
      return y;
   return solve( y % x, x );
}

int main( int argc, char* argv[] ) {
   cout << "HCF of two numbers 12 and 72 is: " << solve(12, 72) << endl;
   cout << "HCF of two numbers 18 and 13 is: " << solve(18, 13) << endl;
   cout << "HCF of two numbers 117 and 96 is: " << solve(117, 96) << endl;
   cout << "HCF of two numbers 85 and 15 is: " << solve(85, 15) << endl;
}

输出

HCF of two numbers 12 and 72 is: 12
HCF of two numbers 18 and 13 is: 1
HCF of two numbers 117 and 96 is: 3
HCF of two numbers 85 and 15 is: 5

结论

在解决不同数学问题时，求最大公因数或最大公约数是非常有用的。可以使用欧几里得方法来计算。这个方法可以迭代地应用，也可以递归地应用。这里我们展示了两种方法。另一方面，我们可以通过最小公倍数（LCM）来计算GCD/HCF。两个数的GCD和LCM与这两个数的乘积相同。因此，根据这个原理，如果我们知道这两个数的LCM和乘积，就可以很容易地计算出GCD。