유클리드 호제법

일반적으로 최대공약수(Greatest Comon Divisor: GCD)는 소인수 분해를 통해 공통된 소수의 곱으로 구할 수 있다.
이는 알고리즘에서 사용하기엔 비효율적이다. 유클리드 호제법은 조금 더 간단하게 최대공약수를 구할 수 있다.

유클리드 호제법은 $O(logN)$의 시간 복잡도를 보인다.

유클리드 호제법의 원리

유클리드 호제법의 기본이 되는 연산은 % 연산이다.

1. 큰 수를 대상으로 작은 수를 % 연산을 한다.
2. 작은 수와 결과로 나온 값을 대상으로 1번을 반복한다.
3. 2번을 반복하다가 나머지가 0이 되는 시점의 작은 수가 GCD가 된다.

유클리드 호제법의 예시

예를 들어, 270과 192의 GCD를 구해야 한다고 해보자.

270 % 192 = 78
      192 % 78 = 36
            78 % 36 = 6
                 36 % 6 = 0

∴ GCD = 6

유클리드 호제법의 구현

유클리드 호제법은 재귀를 이용하여 손 쉽게 구현할 수 있다.

int GCD(int a, int b)
{
    if(b == 0)
        return a;
    else
        GCD(b, a % b);
}

최소공배수

유클리드 호제법을 이용하여 두 수의 GCD를 구하는 방법에 대해서 알아봤다.
GCD를 이용하여 두 수의 최소공배수(Least Common Multiple: LCM)을 구할 수도 있다.

예를 들어 두 수 A와 B가 주어졌을 때 LCM은 다음과 같이 구할 수 있다.

$LCM = \cfrac{A \times B}{GCD(A, B)}$

앞선 예시로 270와 192의 LCM은 다음과 같이 구할 수 있다.

270 × 192 = 51840
51840 ÷ GCD(270, 192) = 51840 ÷ 6
                     = 8640

마무리

만약 두 수가 아닌 여러 수의 GCD를 구해야 한다면 유클리드 호제법을 여러번 적용하면 된다.
다음에는 항등식에 적용할 수 있는 확장 유클리드 호제법에 대해서 알아보도록 하겠다.