[Java] 유클리드 호제법 (Euclidean Algorithm)

📌 유클리드 호제법이란?

• 두 개의 수가 자연수가 주어졌을 때 최대공약수(GCD)를 구하는 알고리즘을 말한다.

여기서 GCD 란?
Greatest Common Divisor. 즉 가장 큰 공통된 약수라는 의미다.

// 최대공약수 구하기
public static int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

 

• 코드는 재귀를 사용하여 'b'와 'a'의 나머지를 'b'로 나눈 나머지를 'b'가 0이 될 때까지 반복적으로 호출합니다. 이 시점에서 GCD로 'a'를 반환합니다.
• 나머지가 0이라면 해당 수가 최종 최대공약수이다.
• 그렇지 않다면 나머지를 a로 바꾸어 재귀를 반복한다.

 

+) 최소공배수

// 최소공배수 구하기
public static int lcm(int a, int b) {
    int gcd = gcd(a, b);
    return (a * b) / gcd;
}

• 최소 공배수를 구하는 가장 효율적인 방법은 위의 최대공약수를 구할 때 사용한 유클리드 호제법을 이용하여 풀면 된다.
• 두 수의 최대 공약수를 유클리드 호제법을 통하여 구한다.
• 두 수 A, B를 곱한 뒤 최대 공약수로 나눈 값을 최소 공배수로 출력한다.