[알고리즘] 유클리드 호제법 (GCD)

유클리드 호제법 (GCD)

💡 유클리드 호제법은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘 중 하나이다.

• 호제법 = 두 수가 서로 상대방 수를 나누어 결국 원하는 수를 얻는 알고리즘을 말한다.
• 명시적으로 기술된 알고리즘 중 가장 오래되었다고 알려져 있다.

 

원리

1️⃣ 2개의 자연수 a,b 에 대하여 a를 b로 나눈 나머지가 r이면 (단, a>b) , a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

2️⃣ 이 성질을 이용해 이번에는 b를 r로 나눈 나머지 r2 를 구하고, 다시 r을 r2 로 나눈 나머지를 구하는 과정을 반복해서 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수인 것이다.

 

접근방법

1️⃣ 반복문을 이용한 방법

2️⃣ 재귀를 이용한 방법

int GCD(int a, int b){
	while(b!=0){
		int r = a % b; //나머지 
		a = b; //b 대입.
		b = r; //r 대입. //쭉 반복 
	}
	return a;
}

int GCD(int a, int b) {
	if(a%b==0){
		return b;
	}
	return GCD(b, a%b);
}