Java에서 숫자 배열의 최소공배수(LCM) 구하는 방법

최소공배수(LCM)란 무엇인가?

최소공배수(L.C.M., Least Common Multiple)는 두 수가 공통으로 가지는 배수 중 가장 작은 양의 정수를 의미합니다.

예를 들어 3과 4의 배수는 각각 다음과 같습니다.

• 3 → 3, 6, 9, 12, 15 ...
• 4 → 4, 8, 12, 16, 20 ...

두 수의 배수 목록에서 가장 먼저 만나는 공통 값은 12입니다. 따라서 3과 4의 최소공배수는 12가 됩니다.

배열의 LCM을 구하는 예제 프로그램

다음 예제는 배열에 담긴 여러 개의 숫자에 대해 최소공배수를 계산하는 Java 코드입니다.

public class LCMofArrayOfNumbers {
    public static void main(String args[]) {
        int[] myArray = {25, 50, 125, 625};
        int min, max, x, lcm = 0;
        
        for(int i = 0; i<myArray.length; i++) {
            for(int j = i+1; j<myArray.length-1; j++) {
                if(myArray[i] > myArray[j]) {
                    min = myArray[j];
                    max = myArray[i];
                } else {
                    min = myArray[i];
                    max = myArray[j];
                }
                for(int k =0; k<myArray.length; k++) {
                    x = k * max;
                    if(x % min == 0) {
                        lcm = x ;
                    }
                }
            }
        }
        System.out.println("LCM of the given array of numbers : " + lcm);
    }
}

실행 결과

LCM of the given array of numbers : 250

더 효율적인 방법: GCD(최대공약수) 활용하기

위 방식보다 더 간결하고 효율적인 방법은 최대공약수(GCD)를 이용하는 것입니다. 두 수 a와 b의 최소공배수는 다음 공식으로 구할 수 있습니다.

LCM(a, b) = (a × b) / GCD(a, b)

배열 전체의 최소공배수는 첫 번째 요소부터 시작해 인접한 두 값씩 순차적으로 위 공식을 적용하며 누적하면 됩니다.

public class LCMofArray {
    // 유클리드 호제법으로 최대공약수 계산
    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public static void main(String[] args) {
        int[] arr = {25, 50, 125, 625};
        int lcm = arr[0];

        for (int i = 1; i < arr.length; i++) {
            lcm = lcm * arr[i] / gcd(lcm, arr[i]);
        }

        System.out.println("배열 숫자들의 최소공배수 : " + lcm);
    }
}

이 코드는 {25, 50, 125, 625} 배열에 대해 정확한 최소공배수인 1250을 출력합니다. 반복문 중첩 없이 선형 시간에 처리되므로 실무에서는 GCD 기반 방식을 사용하는 것이 좋습니다.