유클리드 호제법 이론 (최대 공약수 구하기)

원리

즉, a, b의 최대공약수와 b, r의 최대공약수가 같음을 이용해서 최대공약수를 빠르게 구하는 방법이다.

 

예를들어

78696과 19332의 최대 공약수를 구하고자 한다면

78696 = 19332 * 4 + 1368

19332 = 1368 * 14 + 180

1368 = 180 * 7 + 108

180 = 108 * 1 + 72

108 = 72 * 1 + 36

72 = 36 * 2 + 0

최대공약수가 36가 된다

 

위의 예시를 보면 알겠지만

a와 b의 최대 공약수를 구할때

a에다가 b를 나눈 몫에 나머지를 나누는것을

나머지가 0이 될때 까지 반복하면 된다.

 

확장된 유클리드 호제법과 코드

확장된 유클리드 호제법 (gcd)