유클리드 호제법 (Euclidean Algorithm)

유클리드 호제법 (Euclidean Algorithm)

유클리드 호제법은 두 정수의 최대 공약수(Greatest Common Divisor, GCD)를 효율적으로 찾는 알고리즘

• 최대 공약수 (GCD) 구하기

1. 두 수 a와 b를 입력 받습니다 (단, a > b).
2. a를 b로 나눈 나머지를 r로 합니다 (r = a % b).
3. b를 a에 할당하고, r을 b에 할당합니다.
4. b가 0이 아닐 때까지 2번과 3번 과정을 반복합니다.
   a의 값이 최대 공약수(GCD)가 됩니다.

• 최소 공배수 (LCM) 구하기
  최소 공배수는 두 수 a와 b의 곱을 두 수의 최대 공약수로 나눈 값으로 계산할 수 있습니다. 즉, lcm(a, b) = (a * b) / gcd(a, b)입니다.

1. 먼저 두 수의 최대 공약수를 찾습니다 (위의 GCD 알고리즘 사용).
2. 두 수를 곱한 값을 최대 공약수로 나눕니다: (a * b) / GCD.

Java코드로 나타내기

public class Main {
    public static void main(String[] args) {
        // 두 수를 정의합니다.
        int num1 = 48;
        int num2 = 18;

        // 최대 공약수를 계산합니다.
        int gcd = gcd(num1, num2);

        // 최소 공배수를 계산합니다.
        int lcm = lcm(num1, num2, gcd);

        // 결과를 출력합니다.
        System.out.println("최대 공약수: " + gcd);
        System.out.println("최소 공배수: " + lcm);
    }

    // 최대 공약수를 구하는 메서드
    private static int gcd(int a, int b) {
        while (b != 0) {
            int temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }

    // 최소 공배수를 구하는 메서드
    private static int lcm(int a, int b, int gcd) {
        return (a * b) / gcd;
    }
}