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

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

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

 

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

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

 

 

 

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

$$\begin{array}{rl}GCD(a,b,c)& =GCD(GCD(a,b),c)\\ LCM(a,b,c)& =LCM(LCM(a,b),c)\end{array}$$

세 수, 그 이상 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{array}{rl}192& =2^6\times 3\\ 72& =2^3\times 3^2\\ \therefore GCD(192,72)& =2^3\times 3=24\end{array}$$

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

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

 

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

$a$를 $b$로 나눈 나머지를 $r$이라고 했을 때, 즉 $a$이라고 했을 때, $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 함수가 추가됐습니다. 구현 방식은 똑같이 유클리드 호제법으로 되어있습니다.