유클리드 호제법

유클리드 호제법

유클리드 호제법은 두 개의 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘입니다.

• 두 자연수 A,B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 합시다.
• 이때 A와 B의 최대공약수는 B와 R의 최대공약수와 같습니다.

유클리드 호제법의 아이디어를 그대로 재귀함수로 작성할 수 있습니다.

<예시>
192와 162의 최대공약수를 구한다고 할 때, 192와 162를 각각 A와 B라고 하겠습니다. 
A와 B의 최대공약수는 B와 나머지 R의 최대공약수와 같으므로 A와 B를 각각 B와 R로 초기화해줍니다. 
이를 A를 B로 나눈 나머지가 0이 나올때까지 반복하면 다음과 같습니다.  

i=1) A=192, B=162
i=2) A=162, B=30
i=3) A=30, B=12
i=4) A=12, B=6

이때 4번의 단계를 거쳐 나온 B(6)가 192와 162의 최대공약수가 됩니다. 

이 과정을 파이썬 코드로 구현하면 다음과 같습니다.

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

print(gcd(192,162))

# 실행결과 6