[Java/알고리즘] 유클리드 호제법 - 최대공약수, 최소공배수

유클리드 호제법

유클리드 호제법은 두 수의 최대공약수(GCD)를 찾기 위한 알고리즘이다.

1. 두 수 중 큰 수를 작은 수로 나눈다.
2. 나머지가 0이면 작은 수가 최대 공약수
3. 나머지가 0이 아니면 작은 수가 큰 수가되고, 나머지를 작은 수로 대체하여 1단계로 돌아간다.

즉, 큰 수를 작은 수로 나눠 나머지가 0이 될 때까지 반복하는 방식이다.

---

최대공약수(GCD) 구현

// 재귀 방식
public int gcd(int a, int b) {
    if( b == 0 ) return a;
    return gcd(b, a % b);
}

최소공배수(LCM) 구현

최대공약수(gcd)를 이용해 최소공배수를 구한다. 최소공배수는 두 수의 곱에 최대 공약수를 나눈 값과 같다.

public int lcm(int a, int b) {
    return a * b / gcd(a, b);
}