최대공약수(GCD)와 최소공배수(LCM) 구하는 알고리즘

이런 저런 문제를 풀 때, 많이 응용되는 것이 최대공약수(Greatest Common Divisor, GCD)와 최소공배수(Least Common Multiple, LCM) 입니다. 이 포스트에서는 이 두개를 구하기 위한 알고리즘을 다룰 것 입니다.

유클리드 호제법

두 양의 정수 a, b에 대해서 b = aq + r (0 <= r < a)라 하면 a, b의 최대 공약수는 a, r의 최대 공약수와 같다는 원리입니다. 우선 이 말만 듣고는 잘 이해가 안되실 것 입니다.

최대공약수를 구하는 방법

유클리드 호제법으로 재귀와 반복문을 이용하여서 최대공약수(Greatest Common Divisor)를 구하는 알고리즘을 구현할 수 있습니다..

1.재귀함수를 이용한 구현

int gcd(int a, int b) {
    if(b == 0) return a;  // b == 0이면 더 이상 최대공약수를 갖지 않기 때문에 a를 반환한다.
    else gcd(b, a%b);  // 유클리드 호제법을 활용하여서 a, b의 최대 공약수를 b, r(a%b)로 치환한다.
}

2.반복문을 이용한 구현

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

    return a;
}

최소공배수를 구하는 방법

최소공배수(Least Common Multiple)는 최대공약수를 구하면 거의 다 구한 값입니다.
서로 곱한 값에서 공통이 부분만 제외해주면 됩니다. 그러면 최소공배수 LCM은 최대공배수 GCD만 구하면 아래와 같이 손쉽게 구할 수 있습니다.

// gcd는 a, b의 최대공약수이다.
int lcm(int a, int b) {
    return a*b/gcd(a,b);
}