최대공약수(Greatest Common Divisor)와 최소공배수(Least Common Multiple)는 소인수분해를 배운 다음 배우게 됩니다. 작은 수를 풀 때는 인수분해를 이용하여 풀지만 큰 수를 알고리즘으로 풀기 위해서는 다른 접근법이 필요합니다.

최대공약수 찾기

최대공약수는 두 수의 공약수 중 가장 큰 수입니다. 12와 15의 약수는 각각 {1, 2, 3, 4, 6, 12}와 {1, 3, 5, 15}입니다. 두 집합의 교집합에서 가장 큰 원소인 3이 최대공약수가 됩니다. 일반적인 수학 과정에서는 두 수를 소인수분해로 쪼갠 후 공통적인 인수의 최소 지수를 모두 곱하면 최대 공약수를 구하도록 배웠습니다.

유클리드 호제법

유클리드 호제법이란 2개의 자연수에서 최대공약수를 구하는 알고리즘으로, 호제법이란 두 수에 대해 서로 상대방 수를 나누어 원하는 수를 얻는 방법을 일컫습니다. 컴퓨터를 이용할 때 가장 유용한 알고리즘으로, 다른 방법들은 인수를 일일히 구해야 하지만 호제법은 그럴 필요없이 한 번의 루프만으로 간단하게 최대공약수를 구할 수 있습니다.

두 수 a, b가 정수이고 a >= b, b != 0일 때, a를 b로 나눈 나머지를 r이라 가정합니다.
a와 b의 최대공약수가 (a,b)라고 할 때, 다음 식이 성립합니다.

(a,b) = (b,r)

즉 a와 b의 최대공약수는 b와 a를 b로 나눈 나머지 r과의 최대공약수와 같습니다.
15와 12로 예를 들어 보면

(15, 12) = (12, 3) = (3, 0) = 3

r이 0이 될 때까지 같은 과정을 반복하면 최대공약수를 찾을 수 있습니다.
코드로 구현해보면 다음과 같습니다.

public static int greatestCommonDivisor(int a, int b) {
    int r;

    while (b != 0) {
        r = a % b;
        a = b;
        b = r;
    }

    return a;
}

최소공배수 찾기

최소공배수는 최대공약수를 이용하여 계산할 수 있습니다. 최소공배수는 두 수의 모든 인수의 합집합의 개념입니다. 두 수 a와 b를 곱하면 모든 인수를 가지게 되나 교집합이 한 번 중복이 됩니다. 중복된 교집합을 제거하기 위해서 최대공약수로 한 번 나누어줍니다.

public static int leastCommonMultiple(int a, int b) {
    return a * b / greatestCommonDivisor(a, b);
}

Reference

https://twpower.github.io/69-how-to-get-gcd-and-lcm
https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95