최대공약수(GCD)와 최소공배수(LCM)

두 정수 \(a, b\)의 공약수는 \(a\)의 약수이자 \(b\)의 약수인 정수입니다.

최대공약수(GCD, Great Common Divisor)는 가장 큰 공약수를 말합니다.

 

두 정수 \(a, b\)의 공배수는 \(a\)과 \(b\) 모두의 배수가 되는 정수입니다.

최소공배수(LCM, Least Common Multiple)는 가장 작은 공배수를 말합니다.

 

 

 

최대공약수, 최소공배수의 성질

\begin{align}
GCD(a,b,c) &= GCD(GCD(a,b),c) \\
LCM(a,b,c) &= LCM(LCM(a,b),c)
\end{align}

세 수, 그 이상 N개의 숫자의 최대공약수, 최소공배수는 위와 같은 식으로 구할 수 있습니다.

 

 

 

최대공약수 구하는 방법

(1) 2부터 \(min(a, b)\)까지 나눠보기 (Brute Force)

int gcd = 1;
for (int i=2; i<=min(a,b); ++i)
    if (a%i==0 && b%i==0)
        gcd = i;

가장 쉬운 방법이지만 \(O(min(a, b))\)의 시간복잡도를 가져 비효율적입니다.

 

(2) 소인수분해 (prime factorization)

두 수를 소인수분해 해서 중복되는 부분을 찾으면 최대공약수가 됩니다.

예를 들어 \(a=192, b=72\)라고 하면

\begin{align}
192 &= 2^{6} \times 3 \\
72 &= 2^{3} \times 3^{2} \\
\therefore GCD(192,72) &= 2^{3} \times 3 = 24
\end{align}

이런 식으로 구할 수 있습니다.

문제는 소인수분해를 하는게 번거롭고 느리다는 겁니다.

 

(3) 유클리드 호제법 (Euclidean algorithm)

\(a\)를 \(b\)로 나눈 나머지를 \(r\)이라고 했을 때, 즉 \(a%b=r\)이라고 했을 때, \(GCD(a, b)=GCD(b,r)\)임을 이용하면 빠르게 구할 수 있습니다. 나머지가 0이 될 때까지 진행하면 최대공약수를 구할 수 있습니다.

 

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

재귀함수를 사용하면 위와 같이 나타낼 수 있고요, Tail Recursion이기 때문에 반복문으로 바꿀 수 있습니다. 재귀 버전은 호출스택이 쌓이기 때문에 메모리를 더 씁니다.

 

int gcd(int a, int b) {
    while (b != 0) {
    	int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

반복문으로 만든 최대공약수 함수입니다. 시간복잡도는 \(O(\log (a+b) ) \)라고 하네요.

참고로 \(a>b\)일때 swap 하도록 하는 사람도 있는데 굳이 그렇게 하지 않아도 알아서 바뀝니다. 이건 숫자 대입해보면 바로 알 수 있습니다.

 

 

 

최소공배수 구하는 방법

최소공배수는 위에서 구한 최대공약수를 활용해 구할 수 있습니다.

\[LCM(a,b)=\frac{a\times b}{GCD(a,b)}\]

두 수의 곱을 최대공약수로 나눠주면 최소공배수가 됩니다.

 

int lcm(int a, int b) {
    return (a*b) / gcd(a, b);
}

위 공식을 그대로 옮긴 함수입니다. 문제가 없어보이지만 \(a \times b\) 부분에서 오버플로우가 발생하기 쉽습니다.

예를 들어 \(lcm(50000, 100000)\)을 계산해보면 당연히 반환값이 100000이 나와야겠지만, 대신 14100이라는 값이 반환됩니다. \(a \times b\)의 값이 50억으로 32비트 정수형의 범위를 넘어가기 때문입니다.

 

int lcm(int a, int b) {
    return a * (b / gcd(a, b));
}

이렇게 미리 한쪽을 gcd로 나눠주면 오버플로우가 발생하지 않습니다.

 

 

 

(참고) 라이브러리 사용 방법

(1) gcc __gcd

gcc 내장 함수중에 최대공약수를 구할 수 있는 함수가 있습니다. (stl_algo.h)

template<typename _EuclideanRingElement>
    _EuclideanRingElement
    __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
    {
        while (__n != 0)
        {
            _EuclideanRingElement __t = __m % __n;
            __m = __n;
            __n = __t;
        }
        return __m;
    }

유클리드 호제법으로 구현돼있습니다. 비표준이니 다른 컴파일러에는 __gcd 함수가 없을 수도 있습니다.

 

(2) (c++17 이상) std::gcd, std::lcm

c++17부터 <numeric> 헤더에 gcd, lcm 함수가 추가됐습니다. 구현 방식은 똑같이 유클리드 호제법으로 되어있습니다.