再帰的ユークリッドアルゴリズムを使用して2つの数値のGCDを見つけるC++プログラム

2つの数値の最大公約数（GCD）は、両方を除算する最大の数値です。

例：63と21の2つの数字があるとします。

63 = 7 * 3 * 3
21 = 7 * 3

したがって、63と21のGCDは21です。

再帰的ユークリッドのアルゴリズムは、正の整数aとbのペアを使用し、bがゼロになるまでbとa％bを返すことによってGCDを計算します。

再帰的ユークリッドのアルゴリズムを使用して2つの数値の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の2つのパラメータがあります。 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;
}