유클리드 호제법 : 최대공약수(GCD)를 구하는 방법

최대공약수(GCD, Greatest Common Divisor)

두 자연수의 공통된 약수 중 가장 큰 수

*최소공배수(LCM)는 두 자연수의 곱 / 최대공약수의 공식으로 구할 수 있다.

유클리드 호제법

유클리드 알고리즘은 2개의 자연수의 최대공약수를 구하는 알고리즘 중 하나로, 두 수가 서로의 상대방 수를 나누어 원하는 수를 얻어내는 접근으로 이루어진다.

접근 방식

비교대상인 두 개의 자연수 a, b (단, a > b)에서 a를 b로 나눈 나머지를 r이라고 했을 때, GCD(a,b) = GCD(b,r)과 같고 r이 0이면, 그 때의 b는 최대공약수이다. 의 원리를 활용한다.

1. 반복문을 이용한 방법

int gcd(int a, int b) {    
		int tmp, n;    // b가 a보다 큰 수가 되도록 swap    
		
		if (a < b) {        
				tmp = a;        
				a = b;        
				b = tmp;   
		}    

		while (b != 0) {  // b가 0이 되는 순간의 a를 GCD로 판단        
				n = a % b;        
				a = b;        
				b = n;    
		}    
		return a;
}

2. 재귀를 이용한 방법

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

참고 자료

[Algorithm] 유클리드 호제법 - 최대공약수(GCD) & 최소공배수(LCM)

[Algorithm] 유클리드 호제법 - 최대공약수(GCD) 구하기