[최대공약수 알고리즘] 유클리드 호제법

최대공약수를 구하는 알고리즘은 다양하겠지만 오늘은 유클리드 호제법에 대해서 알아보고자 합니다. 호제법이라는 말은 두 수가 서로 상대방 수를 나누어 결국에는 원하는 수를 얻어내는 알고리즘입니다.

 

유클리드 호제법

유클리드 호제법은 두 자연수 A와 B의 최대공약수를 구하는 알고리즘입니다. 이때, A가 B보다 크다고 가정합시다. 그렇다면, A를 B로 나누었을 때 나머지가 R이라고 하면, A와 B의 최대 공약수는 B와 R의 최대 공약수와 동일합니다. 말로만 설명하면 무슨 말인지 모르겠으니, 예시를 들어보도록 하겠습니다.

 

예를 들어서, A와 B를 각각 192과 168이라는 자연수로 설정해봅시다. 192를 168로 나누었을 때의 나머지는 24입니다. 따라서 168과 24의 최대공약수를 구하면 됩니다. 24는 168의 약수이므로 최대공약수는 24입니다. 결국 192와 168의 최대공약수는 24 임을 도출할 수 있습니다. 이런 식으로 최대공약수를 구하는 방법이 유클리드 호제법입니다.

 

유클리드 호제법 파이썬 코드

위에서 192와 168의 최대 공약수를 유클리드 호제법으로 구해보았습니다. 이를 파이썬 코드로 표현하면 다음과 같이 표현할 수 있습니다.

def gcd(a,b):
	if a % b == 0:
    	return b
    else:
    	gcd(b, a % b)

print(gcd(192, 168))

마치며

지금까지 유클리드 호제법으로 최대공약수를 구하는 방법을 구해보았습니다. 물론 유클리드 호제법을 이용하지 않더라도 최대 공약수를 구하는 방법은 많이 있겠지만, 그래도 이런 방법도 있다는 것을 알아두면 좋을 것 같습니다.