유클리드 호제법 (최대 공약수, 최소 공배수)

유클리드 호제법은 두 수의 최대공약수(Greatest Common Divisor, GCD)를 계산하는 가장 효율적인 알고리즘입니다. 이를 활용하면 두 숫자의 최소공배수(Least Common Multiple, LCM)도 쉽게 구할 수 있습니다.

 

유클리드 호제법의 원리

유클리드 호제법은 다음 성질을 이용합니다:

1. 두 수 A와 B의 최대공약수는, A와 B를 나눈 나머지(A%B)의 최대공약수와 같습니다.
2. 즉, GCD(A , B) = GCD(B , A%B)
3. 이 과정을 반복하여 나머지가 0이 되었을 때, 그 나누는 값이 최대공약수입니다.

예시: A=24, B=36

1. 24%36=24, 따라서 GCD(24,36) = GCD(36,24)
2. 36%24=12, 따라서 GCD(36,24) = GCD(24,12)
3. 24%12=0, 따라서 GCD(24,12)=12
4. 결과적으로 GCD(24,36)=12

최소공배수와 최대공약수의 관계

최대공약수와 최소공배수는 다음 관계를 만족합니다

\( LCM(A,B) = {A × B \over GCD(A,B)} \)

• 두 수의 곱을 최대공약수로 나누면 최소공배수를 구할 수 있습니다.
• 이 관계를 이용하면, 최대공약수를 계산한 후 최소공배수를 효율적으로 구할 수 있습니다.

코드

public class GCDAndLCM {

    // 최대공약수(GCD) 계산: 유클리드 호제법
    public static int gcd(int a, int b) {
        while (b != 0) { // 나머지가 0이 될 때까지 반복
            int temp = b;
            b = a % b; // a를 b로 나눈 나머지를 b에 저장
            a = temp; // b를 a에 저장
        }
        return a; // 마지막에 남은 a가 최대공약수
    }

    // 최소공배수(LCM) 계산
    public static int lcm(int a, int b) {
        return a * b / gcd(a, b); // LCM 공식: A * B / GCD
    }

    public static void main(String[] args) {
        int a = 24; // 첫 번째 숫자
        int b = 36; // 두 번째 숫자

        // 최대공약수와 최소공배수 계산
        int gcdResult = gcd(a, b);
        int lcmResult = lcm(a, b);

        // 결과 출력
        System.out.println("두 수: " + a + ", " + b);
        System.out.println("최대공약수(GCD): " + gcdResult);
        System.out.println("최소공배수(LCM): " + lcmResult);
    }
}