알고리즘 - 유클리드 호제법(최대 공약수 구하는 방법)과 최소 공배수 구하는 방법에 대해서 (자바)

유클리드 호제 알고리즘

유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다.

 

 

두 수 a, b 의 최대 공약수를 구할 때 사용한다.

단, 전제 조건은 a > b 이어야 한다.

---

최대 공약수와 최소 공배수에 대해서 (개념)

💡 최대공약수(GCD: Greatest Common Divisor)

- 두 수의 공통된 '약수 중에서 가장 큰 수'를 의미.


💡 최소공배수(LCM: Least Common Multiple)

- 두 수의 공통된 '배수 중에서 가장 작은 수'를 의미.

 

 

약수와 배수

약수(Divisors)
- 어떤 수를 나누어 떨어지게 하는 수를 의미
- 10의 약수는 1, 2, 5, 10

 

배수(Multiple)
- 배수는 어떤 수의 배를 이루는 수를 의미
- 24, 36, 48은 12의 배수, 시간의 배수는 1시간의 2배인 2시간을 말합니다.

 

결론적으로는 유클리드 알고리즘을 기반으로 최대공약수를 구하고 이를 기반으로 최소공배수를 구한다.

---

최대 공약수 구현

재귀 방식

1. b가 0이면 a가 최대 공약수가 된다.
2. b가 0이 아니라면 b와 a%b 의 최대 공약수를 나누는 수가 0이 될 때까지 재귀를 타고 반복

public static int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

 

반복문 사용

1. 재귀와 마찬가지로 b가 0이 될 때까지 반복
2. b를 temp에 저장
3. b에 a%b(나머지)를 저장
4. temp를 a에 저장

public static int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

 

최소 공배수 구현

• 최대공약수의 함수를 기반으로 '최소공배수'를 구합니다.

 

• 해당 방식은 두 수 a와 b의 최소공배수를 구하는 함수입니다.
• 함수 내부에서는 a와 b의 최대 공약수를 이용하여 최소 공배수를 계산합니다.
• 최소 공배수는 두 수의 곱에 최대 공약수를 나눈 값과 같습니다.

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