[알고리즘] 최소공배수 lcm

최소공배수(LCM) 구하기

최소공배수(LCM, Least Common Multiple)는 두 수의 공통 배수 중에서 가장 작은 값을 의미합니다. 두 수의 배수는 각각의 수를 1, 2, 3, ... 등의 정수로 곱한 결과로 정의됩니다. 예를 들어, 숫자 4의 배수는 4, 8, 12, 16, ...이고 숫자 6의 배수는 6, 12, 18, 24, ...입니다. 이 두 숫자의 공통 배수 중 가장 작은 값은 12이므로 4와 6의 최소공배수는 12입니다.

배수란?

배수는 어떤 정수 n에 대해 2n, 3n, 4n ...과 같이 n의 배수 % n == 0인 숫자를 의미합니다. 예를 들어, 숫자 5의 배수는 5, 10, 15, 20, ...입니다.

for문으로 최소공배수 구하기

public static void main(String[] args) {
    int n = 10;
    int m = 15;

    System.out.println(lcm(n,m));
}

public static int lcm(int n, int m) {
    int minNum = Math.min(n, m);
    for (int i = minNum; i <= n * m; i+=minNum) {
        if (i % n == 0 && i % m == 0) {
            return i;
        }
    }
    return -1;
}

• 두 수 중 작은 값을 선택하여 최소공배수를 찾기 위한 시작 값으로 설정합니다.
• 최소값부터 시작하여 반복문을 돌면서 i 값을 증가시킵니다. 이때, i가 두 수의 배수인지 확인합니다.
• i % n == 0 && i % m == 0 조건을 만족하는 첫 번째 i 값이 두 수의 최소공배수가 됩니다.

 

 

 

수학적으로 최소공배수 구하기

최소공배수를 구하는 더 효율적인 방법은 두 수의 곱을 최대공약수(GCD)로 나누는 것입니다.

이를 통해 두 수의 공배수 중 가장 작은 값을 빠르게 찾을 수 있습니다.

public static void main(String[] args) {
    int n = 10;
    int m = 15;

    System.out.println("최소공배수 : " + lcm(n,m));
}

public static int lcm(int n, int m) {
    return n * m / gcd(n,m);
}

public static int gcd(int n, int m) {
    while (m != 0) {
        int tmp = n % m; 
        n = m; 
        m = tmp; 
    }
    return n; 
}

두 수의 곱을 최대공약수로 나누어 최소공배수를 구합니다.

n * m은 두 수의 공배수를 의미하며, 이를 최대공약수로 나누면 최소공배수를 얻을 수 있습니다.

 

이 방법은 두 수의 곱을 최대공약수로 나누어 최소공배수를 효율적으로 계산할 수 있는 방법입니다.