C ++程序使用递归Euclid算法查找两个数的GCD
两个数的最大公约数(GCD)是将两个数相除的最大数。
例如：假设我们有两个数字63和21。
63 = 7 * 3 * 3 21 = 7 * 3
因此，GCD分别为63和21。
递归Euclid算法通过使用一对正整数a和b并返回b和a％b直到b为零来计算GCD。
给出了使用递归Euclid算法找到两个数字的GCD的程序，如下所示-
示例
#include <iostream>
using namespace std;
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
int main() {
int a , b;
cout<<"Enter the values of a and b: "<<endl;
cin>>a>>b;
cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
return 0;
}输出结果
上面程序的输出如下-
Enter the values of a and b: 105 30 GCD of 105 and 30 is 15
在上面的程序中，gcd()是一个递归函数。它具有两个参数，即a和b。如果b等于0，则a返回到main()函数。否则，该gcd()函数以b和a％b值递归调用自身。以下代码片段对此进行了演示-
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}在该main()方法中，从用户请求a和b的值。然后gcd()调用函数并显示a和b的GCD值。这在下面看到-
int main() {
int a , b;
cout<<"Enter the values of a and b: "<<endl;
cin>>a>>b;
cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
return 0;
}