최대공약수 알고리즘(유클리드)

유클리드 최대공약수

 

수학자로 유명한 유클리드(Euclid)는 최대공약수에 다음과 같은 성질이 있다는 것을 발견하였다.

 

• a와 b의 최대공약수는 'b'와 'a를 b로 나눈 나머지'의 최대공약수와 같습니다. 즉, gcd(a, b) = gcd(b, a%b)입니다.
• 어떤 수와 0의 최대공약수는 자기 자신입니다. 즉, gcd(n, 0) = n입니다.

ex)

1. 60과 24의 최대공약수

gcd(60, 24) = gcd(24, 60%24) = gcd(24, 12) = gcd(12, 24%12) = gcd(12, 0) = 12

 

2. 81과 27의 최대공약수

gcd(81, 27) = gcd(27, 81%27) = gcd(27, 0) = gcd(27, 0) = 27

 

a와 b의 최대공약수를 구하기 위해서 (a, b)보다 좀 더 작은 숫자인 (b, a%b)의 최대공약수를 구하는 과정을 이용하는 전형적인 재귀호출 문제입니다. (좀 더 작은 값으로 자기 자신을 호출합니다)

 

재귀 호출이 무한히 반복되지않도록 하는데 필요한 종료 조건은 '어떤 수와 0의 최대공약수는 자기 자신'입니다.

즉, b가 0이면 재귀 호출을 멈추고 결과를 돌려줍니다.