재귀 유클리드 알고리즘을 사용하여 두 숫자의 GCD를 찾는 C++ 프로그램

두 숫자의 최대 공약수(GCD)는 두 숫자를 나누는 가장 큰 숫자입니다.

예:63과 21이라는 두 개의 숫자가 있다고 가정해 보겠습니다.

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

따라서 63과 21의 GCD는 21입니다.

재귀 유클리드 알고리즘은 양의 정수 a와 b를 사용하고 b가 0이 될 때까지 b와 a%b를 반환하여 GCD를 계산합니다.

재귀 유클리드 알고리즘을 사용하여 두 숫자의 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()는 재귀 함수입니다. 두 개의 매개변수, 즉 및 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;
}