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;
}