유클리드 호제법, 유클리드 알고리즘

유클리드 호제법

유클리드 호제법(Euclidean algorithm)은 유클리드 알고리즘으로도 불리며, 두 수의 최대 공약수를 구하는 알고리즘이다. 이 유클리드 호제법을 응용해 최소공배수도 구할 수 있으며, 여러가지 방면으로 활용할 수 있다.

최대공약수 구하기

일반적인 방법으로 최대공약수를 구하려면, 소인수분해라는 과정을 거친 이후에 공통된 소수를 찾아 최대공약수를 알 수 있다. 하지만 이 과정은 수가 커질수록 소인수분해가 어려운 단점이 있는데, 유클리드 호제법을 사용하면 이 소인수분해 방법보다 효율적으로 최대공약수를 구할 수 있다.

유클리드 호제법을 사용해 최대공약수를 구해보자. 큰 수인 78696과 19332의 최대공약수를 구하는 과정을 알아보겠다. 단순하게 생각하면 나누어떨어지지않으면 나누어떨어질때까지 과정을 반복한다고 생각하면 된다

1. 78696과 19332는 19332로 나누어떨어지지않는다. $78696 = 19332 * 4 + 1368$ 여기서 19332와 1368을 다음 과정으로 사용한다.

2. 19332와 1368은 1368로 나누어떨어지지않는다. $19332 = 1368 * 13 + 180$

3. 1368과 180은 180으로 나누어떨어지지않는다. $1368 = 180 * 7 + 108$

4. 180과 108은 108으로 나누어떨어지지않는다. $180 = 108 * 1 + 72$

5. 108과 72은 72으로 나누어떨어지지않는다. $108 = 72 * 1 + 36$

6. 72와 36은 36으로 나누어떨어진다. $72 = 36 * 2 + 0$

따라서, 최대공약수는 36이 된다.

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다

사진으로 보면 이해하기가 쉬울 것 같아 위키피디아의 gif를 가져와봤다.

 *https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%ED%98%B8%EC%A0%9C%EB%B2%95*

파이썬에서

파이썬에서 유클리드호제법의 시간복잡도는 O(logN)이다.

파이썬으로 유클리드호제법을 쉽게 구현해줄 수 있다.

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a