[알고리즘/Java] 최대공약수(GCD), 최소공배수(LMC) 함수

 

 

Java에서 최대공약수(GCD) 및 최소공배수(LCM) 를 구하는 방법을 자세히 알아보자.

 

---

1. 최대공약수(GCD) 구하는 방법

🔹 유클리드 호제법 (Euclidean Algorithm)

최대공약수를 구하는 가장 효율적인 알고리즘 중 하나는 유클리드 호제법입니다.

📌 유클리드 호제법 개념

• 두 수 a와 b가 있을 때, a를 b로 나눈 나머지를 r이라고 하면,
  GCD(a, b) = GCD(b, r) 와 같습니다.
• 이 과정을 나머지가 0이 될 때까지 반복하면, 남은 수가 최대공약수입니다.

 

🔹 유클리드 호제법의 예제

예를 들어, **GCD(48, 18)**을 구하는 과정:

1. 48 ÷ 18 = 2 ... 나머지 12
2. 18 ÷ 12 = 1 ... 나머지 6
3. 12 ÷ 6 = 2 ... 나머지 0

➡️ 따라서 GCD(48, 18) = 6.

 

🔹 Java 코드 (재귀 & 반복문 방식)

public class MathUtils {
    // 1. 재귀 함수 사용 (Recursive)
    public static int gcdRecursive(int a, int b) {
        if (b == 0) return a;
        return gcdRecursive(b, a % b);
    }

    // 2. 반복문 사용 (Iterative)
    public static int gcdIterative(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public static void main(String[] args) {
        int a = 48, b = 18;
        System.out.println("GCD (재귀): " + gcdRecursive(a, b));  // 출력: 6
        System.out.println("GCD (반복문): " + gcdIterative(a, b));  // 출력: 6
    }
}

 

---

 

2. 최소공배수(LCM) 구하는 방법

🔹 개념

최소공배수(LCM)는 두 수의 공통 배수 중 가장 작은 값입니다.
LCM을 구하는 공식은 다음과 같습니다.

🔹 Java 코드

public class MathUtils {
    // 최대공약수(GCD) - 반복문 방식
    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

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

    public static void main(String[] args) {
        int a = 48, b = 18;
        System.out.println("LCM: " + lcm(a, b));  // 출력: 144
    }
}

 

---

 

3. 시간 복잡도 분석

1. GCD (유클리드 호제법)
   • 시간 복잡도: O(log min(a, b))
   • 이유: 매 단계에서 나누기를 수행하며 값이 절반 이하로 줄어들기 때문.
2. LCM
   • GCD를 구하는 데 O(log min(a, b)) 걸리고, 곱셈과 나눗셈은 O(1) 이므로
     LCM의 전체 시간 복잡도는 O(log min(a, b)).