[알고리즘] 최소 공배수, 최대 공약수와 유클리드 호제법 (+ 약수 구하기 알고리즘)

2025-06-23 6 분 소요

최소 공배수와 최대 공약수

둘 이상의 음이 아닌 정수가 주어졌을 때, 공배수(Common multiple)는 주어진 정수들의 공통된 배수를 의미하고, 최소 공배수(Least/Lowest Common Multiple, LCM)는 이 공배수 중 가장 작은 수를 의미한다. 한 편 공약수(Common divisor)는 주어진 여러 정수들의 공통된 약수들을 의미하며, 최대 공약수는 그 공약수들 중 가장 큰 수를 의미한다.

한 편, 양의 정수 a, b에 대해 최소 공배수를 L, 최대 공약수를 G라고 한다면 최소 공배수와 최대 공약수는 서로 다음의 관계를 가지고 있다.

\[ L \times G = a \times b \]

이 성질을 이용하면 최소 공배수를 구할 수 있다면 최대 공약수를 구할 수 있게 되고, 반대로 최대 공약수를 알게 되면 최소 공배수를 알게 된다.

최대 공약수 구하기 : 유클리드 호제법 (Euclidean algorithm)

한 편, 두 수의 최대 공약수를 구하는 알고리즘으로 유클리드 호제법이 존재한다. 유클리드 호제법의 개념은 다음과 같다.

두 개의 양의 정수 a, b가 주어져 있고 a ≥ b일 때, a와 b의 최대 공약수는 b와 a를 b로 나눈 나머지 r의 최대 공약수와 동일하다. 그리고 만약 r = 0이라면 b가 a, b의 최대 공약수가 된다.

이를 좀 더 명확하게 정리하자면, 두 양의 정수 a, b의 최대공약수를 구하는 함수를 gcd(a, b)라고 가정하면, gcd(a, b) = gcd(b, r) (단, r = a % b)와 같으며, 만약 r = 0이라면 gcd(a, b) = gcd(b, r) = b라는 것이 유클리드 호제법이다.

이 유클리드 호제법을 이용하여 15와 10의 최대 공약수를 구해보면 다음의 과정을 거친다.

a	b	r = a % b
15	10	5
10	5	0

a = 10, b = 5일 때 r = 0이므로 최종적으로 15와 10의 최대 공약수는 5가 되는 것이다.

자바 언어를 이용하여 유클리드 호제법을 다음과 같이 구현할 수 있다.

// 재귀 함수 사용
public static int getGcdRecursive(int a, int b) {
    if (b == 0) {
        return a;
    }

    return getGcdRecursive(b, a % b);
}

// 반복문 사용
public static int getGcdLoop(int a, int b) {
    int r = -1;
    while (r != 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

코드 1-1. 유클리드 호제법을 구현하는 두 가지 방법.

앞서 언급했듯, 최대 공약수를 알면 최소 공배수도 알 수 있으므로 다음과 같이 최소 공배수를 구하는 함수(메서드)도 구현할 수 있다.

public static int getLcm(int a, int b) {
    int g = getGcdLoop(a, b);
    return (a * b) / g;
}

코드 1-2. 유클리드 호제법으로 구한 최대 공약수를 이용하여 최소 공배수를 구하는 메서드.

유클리드 호제법의 복잡도

유클리드 호제법을 이용할 때 필요한 총 나눗셈 횟수는 두 정수 중 가장 작은 수의 십진법 자릿수의 5배를 초과할 수 없다고 하는데, 이를 라메의 정리라고 한다. 예를 들어 두 정수 중 가장 작은 수가 12일 때 이 수의 자릿수는 2자리이므로 필요한 나눗셈의 횟수는 2 * 5 = 10회를 넘길 수 없다는 것이다. 이로 인해 유클리드 호제법의 시간복잡도는 두 수 중 작은 수를 N이라 할 때 \(O(log N)\) 이라고 한다.

공간복잡도는 반복문을 사용하는 경우 위 코드에서 보듯 최대 변수 3개로만 사용해도 되기에 \(O(1)\)이고, 재귀 함수를 사용할 경우 나눗셈의 횟수만큼 호출 스택의 메모리 용량을 차지하기 때문에 \(O(log N)\)이 된다.

참고로 유클리드 호제법이 아닌 기존의 무차별 대입(Brute force) 방식으로 최대 공약수를 구하는 방법은 다음과 같다. 주어진 두 정수를 a, b라 하고, 이 중 가장 작은 수를 b이라 할 때, b부터 1까지 하나씩 감소시키면서 반복문을 돌도록 하고, 반복문 내 현재 반복 횟수를 담은 변수 i에 대해, a % i == 0 && b % i == 0를 만족할 때, 즉 a를 i로 나눈 나머지가 0이고, 그와 동시에 b를 i로 나눈 나머지도 0임을 만족하는 가장 큰 i값이 최대 공약수가 된다. 이 경우, 두 정수 중 작은 수를 N이라 할 때 최악의 경우 N번까지 반복문을 돌면서 해를 구하므로 시간복잡도는 \(O(N)\)이 된다. 이에 비하면 유클리드 호제법은 상대적으로 효율적인 알고리즘임을 알 수 있다.

번외: 약수를 구하는 가장 효율적인 알고리즘

어떤 자연수 n이 있을 때, 이 자연수의 약수들을 구하려면 어떻게 해야할까? 가장 단순한 방법은 n을 1부터 n까지의 수로 차례대로 나눴을 때 나머지가 0인 수들만 골라내는 것이다. 자바 언어를 이용하여 이를 구현하면 다음과 같다.

public static List<Integer> getDivisorsByBF(int n) {
    List<Integer> divisors = new ArrayList<>();
    for (int i = 1; i <= n; ++i) {
        if (n % i == 0) {
            divisors.add(i);
        }
    }
    return divisors;
}

코드 2-1. 무차별 대입법(Brute force)으로 자연수 n의 약수들을 구해 반환하는 메서드.

그런데 약수들을 관찰해보면 사실 이것보다 조금 더 적은 횟수를 이용하여 모든 약수들을 구할 수 있음을 알 수 있다. 예를 들어 12라는 수의 약수는 [1, 2, 3, 4, 6, 12]이다. 그런데 이 약수들의 배열을 정가운데를 기준으로 데칼코마니마냥 반으로 접는다고 가정했을 때 만나는 두 수를 짝 지으면 이 두 수를 곱했을 때 항상 12가 나온다.

1 * 12 = 12
2 * 6 = 12
3 * 4 = 12

사실 이는 당연한 정보이다. 자연수 n의 약수가 d라고 한다면, n을 d로 나눈 몫 q에 대해 n = qd를 만족하므로 q도 당연히 n의 약수가 되기 때문이다.

이 사실을 토대로 12의 약수들을 다시 살펴보면, 여기서 잠시 12를 n이라고 해보고, 오름차순으로 정렬된 12의 약수들에 대해 가장 작은 수부터 \(d_1,\ d_2,\ d_3,\ d_4,\ d_5,\ d_6\)이라고 한다면, \(n = d_1d_6 = d_2d_5 = d_3d_4\)를 만족함을 알 수 있다. 이를 일반화하면, 자연수 n의 약수가 k개가 있고, 이들을 오름차순 정렬했을 때 각각의 약수들을 \(d_1,\ d_2,\ …,\ d_k\) 라고 할 때, i번째 약수 \(d_i\)에 대해 \(n = d_id_{k-i+1}\)를 만족한다. 이 때, 특수한 경우로 16 = 4 * 4처럼 \(d_i = d_{k-i+1} \equiv d_c\) 인 경우, \(n = d_c^2 \implies d_c = \sqrt{n}\) 을 만족한다. 한 예로 16의 약수들을 오름차순으로 정렬해보면 [1, 2, 4, 8, 16]으로 가운데에 위치한 약수가 4이고, 4 * 4 = 16임을 알 수 있다. 약수들을 오름차순으로 정렬한 뒤 가운데에 위치한 수를 \(d_c\)라 할 때(사실 c = k / 2이다), i ≤ c의 범위에서 \(d_i \le d_c = \sqrt{n}\)의 관계를 만족한다. 따라서 어떤 자연수 n의 약수들을 구할 때 1부터 n까지 반복문을 돌지 않고 1부터 n의 제곱근까지만 반복문을 돌아도 모든 약수들을 구할 수 있는 것이다.

위에서 언급한 사실들을 정리하면 다음과 같다.

어떤 자연수 n과 d가 있을 때 d가 n의 약수라면 n을 d로 나눈 값 n/d 도 n의 약수가 된다. 이를 조금 더 정리해보자면, 어떤 자연수 n의 모든 약수들의 개수가 k라고 하고, 이 약수들의 배열을 오름차순으로 정렬했을 때의 각각의 약수들을 \(d_1,\ d_2,\ …,\ d_k\)라고 할 때, i번째 약수 \(d_i\)와 (k - i + 1)번째 약수 \(d_{k - i + 1}\)에 대해서 \(n = d_id_{k - i + 1}\)를 만족한다.
자연수 n의 모든 약수들을 오름차순으로 정렬했을 때 가운데에 위치한 약수를 \(d_c\)라고 할 때, 특별한 경우는 i번째 약수와 (k - i + 1)번째 약수가 동일할 경우로, 이 경우 \(n =d_c^2 \implies d_c = \sqrt{n}\)을 만족한다. 이로 인해, i ≤ c의 범위에서 \(d_i \le \sqrt{n}\) 을 만족한다.
위 1과 2의 사실을 통해, 자연수 n의 약수들을 모두 구하려면 1부터 \(\sqrt{n}\) 까지만 반복문을 돌아도 모든 약수들을 찾을 수 있다.

이 방법은 단순무식하게 1부터 n까지 약수를 구하는 방법의 시간복잡도 \(O(N)\)에 비해 n의 제곱근까지만 반복문을 돌면 되므로 \(O(\sqrt{n})\)의 시간복잡도를 가져 더 효율적인 알고리즘이 된다.

다음은 위 방법대로 어떤 자연수의 모든 약수들을 찾는 것을 코드로 구현한 것이다.

public static List<Integer> getDivisorsBySqrt(int n) {
    List<Integer> divisors = new ArrayList<>();
    final int L = (int) Math.sqrt(n);
    for (int i = 1; i <= L; ++i) {
        int q = n / i;
        int r = n % i;
        if (r == 0) {
            divisors.add(i);
            if (q != i) {
                divisors.add(q);
            }
        }
    }
    divisors.sort((a, b) -> a - b); // 보기 좋게 오름차순 정렬. 사실 안해도 된다.
    return divisors;
}