최대공약수를 빠르게 구하는 알고리즘 - 유클리드 호제법

1. 최대공약수

 

두 자연수 a,b가 공통으로 가지는 약수중에서 가장 큰 약수를 최대공약수라고 부른다.

 

중요한 성질중 하나는 최대공약수의 약수는 a,b의 공약수이다.

 

 

2. 유클리드 호제법

 

두 양의 정수 a,b (a>b)에 대하여 a = bq + r ( r은 0이상 b 미만)이라고 하면, a,b의 최대공약수는 b,r의 최대공약수와 같다.

 

즉, gcd(a,b) = gcd(b,r)이다. 

 

만약 r=0이라하면, a,b의 최대공약수는 b이다.

 

 

 

3. 유클리드 호제법 활용

 

단 1번만 사용해서는 그 진짜 힘을 알 수 없다.

 

a = bq + r이면 a,b의 최대공약수는 b,r의 최대공약수와 같다

 

b를 r로 나눠서 b = rq2 + r2라는 식을 얻는다면, 결국 b,r의 최대공약수는 r,r2의 최대공약수와 같다.

 

여기서 r을 r2로 나눠서 r = r2 * q3 + r3라는 식을 얻는다면, r, r2의 최대공약수는 r2, r3의 최대공약수와 같다.

 

.. 이를 계속 반복하다보면 언젠가는 나머지가 0인 부분이 존재할것이다.

 

그런 rn = r(n+1) * q(n+2) 라고 한다면, a,b의 최대공약수는 몫인 r(n+1)과 같다.

 

이것을 파이썬 코드로 나타낸다면...

 

while b != 0:
    
    a,b = b, a%b

gcd = a

 

a = bq + r  >>>>>>> b = rx + c로 변하는데, a자리에 b를 넣고, b자리에는 a를 b로 나눈 나머지를 넣었다

 

그리고 이게 나머지가 들어갈 b가 0이 될때까지 반복한다면...

 

r(n) = r(n+1) * q(n+2) + 0 이잖아

 

그 다음에 r(n+1)이 a에 들어가고 b에는 0이 들어가고 반복문을 탈출하겠지

 

그리고 이 r(n+1)이 들어간 a가 a,b의 최대공약수가 된다

 

 

참조

 

https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95