C++程序计算最大公因数

最大公因数（HCF）或最大公约数（GCD）是可以最大程度地整除两个或多个值的因数，并且不会产生任何余数。在本文中，我们将讨论在 C++ 中计算两个数字之间 HCF/GCD 的几种方法。

这仅仅是一个数学解法，并且存在多种算法可以找到 GCD。用于查找 GCD 的欧几里得算法很常见。我们将使用相同的算法以迭代模式和递归模式。

使用迭代方法

欧几里得 gcd 查找算法的迭代解法在算法部分显示。

算法

  • 将两个数字 a 和 b 作为输入。
  • 如果 a 为 0，则返回 b。
  • 如果 b 为 0，则返回 a。
  • 当 a 和 b 不相等时，执行以下操作。
    • 如果 a > b，则 a := a – b。
    • 否则 b := b - a。
  • 结束循环。
  • 返回 HCF 作为变量 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

结论

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

更新于: 2023年4月4日

2K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告