c++ / 최대공약수(GCD) 구하기 (재귀함수 사용)

최대공약수(GCD) 구하기 (재귀함수 사용)

c++ 언어 사용

 

 

 

문제 : 

최대공약수(GCD)값을 구하는 함수인 gcd를 구현하는 것으로, 아래 주어진 코드를 완성하라. 참고로, 주어진 gcd 함수의 입력 파라미터(input parameter) 중 첫번째 값이 두번째 값보다 작은 값이 입력되어 들어갈 것이다.

#include <iostream>
using namespace std;

void gcd(int &a,int &b);

int main()
{
	int a, b, tmp;
	while(1) {
		cout << "두 개의 양의 정수를 입력하세요." << endl;
		cout << "첫 번째 정수 => "; 
		cin >> a;
		cout << "두 번째 정수 => "; 
		cin >> b; 

		if(b > a) {
			tmp = a; 
			a = b; 
			b = tmp;
		}
		cout << "입력한 두 정수의 최대공약수 => ";
		gcd(a,b);
		cout << a << endl;
	}
	return 0;
}

void gcd(int &a, int &b) {
	// 구현 필요
} 

 

 

 

조건 :

1. 재귀 함수(Recursive Function)를 사용한다. 

2. 유클리트 호제법(Euclidean algorithm)을 사용한다.

 

 

 

풀이 코드 :

void gcd(int &a,int &b){ 
	if(b != 0){
		int c = b; 
		b = a % b;
		a = c;
		gcd(a, b); 
	}
}

 

 

 

실행 결과 : 

두 개의 양의 정수를 입력하세요.
첫 번째 정수 => 50
두 번째 정수 => 55
입력한 두 정수의 최대공약수 => 5