[JAVA] 최대 공약수와 최소 공배수 구하기

알고리즘 문제를 풀다보면 최대 공약수와 최소 공배수를 가끔 볼 때가 있는데 이에 대해 정리를 좀 해보려고 한다.

먼저 최대 공약수 자바코드는 다음과 같다.

public int GCD(int a, int b) {
        while(true) {
            if(a % b == 0)
                return b;
            int r = a % b;
            a = b;
            b = r;
        }
    }

여기서 최대 공약수를 구하기 위해 유클리드 호제법을 사용했는데 위키백과에 따르면 유클리드 호제법은 다음과 같다.

즉 a mod b를 했을 때 나머지를 r이라고 하면 a, b의 최대 공약수는 b와 r의 최대 공약수와 같고 r = 0이면 b가 최대 공약수라는 것이다. 이걸 코드로 표현하면 위와 같은데 여기서 a ≥ b라는 조건때문에 크기를 비교하여 a, b를 설정하는 코드를 가끔 보는데 굳이 그렇게 하지 않아도 된다.

위 조건을 만족하는 경우는 상관없고 만족하지 않는 경우에는 %연산 과정에서 자리가 바뀐다. 예를 들어 a = 17과 b = 19라고 가정하면 a mod b = 17 mod 19 = 17이다. 위 코드에서는 mod 연산 결과를 r로 두기 때문에 b를 a에 할당하고 r을 b에 할당하는 과정에서 19 mod 17로 자리가 바뀐다.

 

다음으로 최대 공배수를 구하는 코드는 다음과 같다.

public int LCM(int a, int b) {
        return a * b / GCD(a, b);
    }

두 수를 곱한다는 것은 두 수를 이루는 소수를 모두 곱하는 것과 같다. 이때 최대 공약수를 이루는 소수가 중복해서 곱해지는데 이를 방지하기 위해 두 수의 곱을 최대 공약수로 나눠주면 각자 소수와 공약수를 한번 곱한 것과 같다.

예를 들어 일반적으로 12 와 16의 최소 공배수를 구하는 방법은 다음과 같다.

이때 12와 16을 곱하면 (2 * 2) * (2 * 2) * 3 * 4로 최대 공약수 4가 2번 곱해진다. 이를 방지하기 위해 (12 * 16) / 4를 해주면 2번 곱한 최대 공약수가 1개 사라지면서 우리가 원하는 (2 * 2) * 3 * 4를 만들 수 있다.

 

위 두 가지를 응용하면 2개 이상의 수에 대해서도 최소 공배수를 알 수 있다.

먼저 임의의 두 수에 대해 최소 공배수를 구한뒤 구한 공배수와 나머지 수에 대해서 공배수를 구하면 구할 수 있다.