最高公因数或最大公约数是能够在不产生任何余数的情况下，能够同时整除两个或多个值的因数。在本文中，我们将讨论在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
使用迭代方法
可以使用递归方法来实现相同的欧几里得方法。下面我们将描述递归方法的定义，如下所示的算法。
立即学习“C++免费学习笔记（深入）”；
算法
- 定义一个名为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。
