Euclidean algorithm - 유클리드 호제법

서론

크.... 내가 유클리드 호제법에 대해서 포스팅하는 날이 올줄이야...

상상도 못했다 ㅋㅋㅋ

 

이론

임의의 두 정수가 있을 때 두 정수의 최대공약수를 구하는 방법 중 하나가 유클리드 호제법이다.

여기서 최대공약수는 Greatest Common Divisor이며, 보통 GCD라고 이야기한다.

 

이를 간단히 식으로 표현해보면

a mod b = r = GCD(a, b) = GCD(b, r)

이다.

 

이론 자체는 매우 쉽다.

증명하기가 어려워서 그렇지... ㅋㅋ

 

방식은 아래와 같다.

 

임의의 정수 a와 b가 a > b라고 가정하자.

이 때 b로 a를 나눈 나머지를 r1이라고 하자.

이 r1으로 다시 b를 나누고 이 나머지를 r2라고 하자.

이 r2로 다시 r1을 나누고...

이렇게 나눠 나머지가 0이 될때까지 반복하면 r(n-1)이 최대공약수가 된다.

 

이를 다시 수식으로 표현하면

a mod b = r1

b mod r1 = r2

r1 mod r2 = r3

...

r(n-1) mod r(n) = 0

r(n-1) = GCD

가 된다.

 

소스코드

이를 간단히 파이썬으로 구현해보면 아래와 같다.

 

a = int(input())
b = int(input())

if a < b:
    a,b = b,a

while 1:
    r = a % b
    if r == 0:
        GCD = b
        break
    a,b = b,r

print('GCD = ', GCD)