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

유클리드 호제법

유클리드 호제법이란 다음의 성질을 이용하여 최대공약수 (Greatest Common Divisor, GCD) 를 구하는 알고리즘이다:

 

두 수 A와 B가 있다고 하자 (A > B) 이 때, A와 B를 나눈 나머지 R이라고 할 때,
A와 B의 최대 공약소는 B와 R의 최대 공약수와 같다.

 

 

한 마디로 GCD(A,B) = GCD(B, R)이 성립한다는 건데, 조금 생각해보면 이 특징으로부터 재귀적인 성질을 도출할 수 있음을 알 수 있다. 즉, B과 R 역시 B > R이 성립하므로 B를 R로 나눈 나머지를 X라고하면

결국 GCD(A,B) = GCD(B,R) = GCD(R,X) = ... 이 성립한다. 이 때, 두 값을 나눈 나머지가 0일 때 값들의 약수는 하나이므로 최종적으로 최대공약수를 구할 수 있다.

 

예를 들어, GCD(6, 4) = GCD(4, 2) = GCD(2, 0) = 2 이므로

B 값이 0이 될때까지 주어진 두 수의 나머지에 대한 GCD를 재귀적으로 구할 수 있다.

 

이걸 코드로 구현하면

def GCD(A, B):
	""" A > B """
	if B == 0: return A
    return GCD(B, A%B)

 

 

끝 ◼︎