[알고리즘] 최대공약수 gcd

최대공약수란?

최대공약수(GCD, Greatest Common Divisor)는 두 개 이상의 수의 공통된 약수 중에서 가장 큰 값을 말합니다.

약수란?

약수는 어떤 정수 n을 나누었을 때 나머지가 0이 되는 수를 의미합니다. 예를 들어, 10의 약수는 1, 2, 5, 10입니다. 이 숫자들은 모두 10을 나누었을 때 나머지가 0이 됩니다.

약수 구하기

public static void main(String[] args) {
    int n = 10;

    for (int i = 1; i <= n; i++) {
        if (n % i == 0) {
            System.out.println(i);
        }
    }
}

위 코드는 1부터 n까지 반복문을 돌리면서 n을 i로 나누었을 때 나머지가 0인 숫자를 구하는 코드입니다.

n과 m의 공통된 약수 구하기

public static void main(String[] args) {
    int n = 10;
    int m = 15;

    int minNum = Math.min(n, m);

    for (int i = 1; i <= minNum; i++) {
        if (n % i == 0 && m % i == 0) {
            System.out.println(i);
        }
    }
}

// 출력 값
1
5

위 코드는 n과 m의 공통된 약수를 구하는 방법입니다.

여기서 Math.min(n, m)을 사용하여 더 작은 수까지 반복하는 이유 :

두 수의 공통 약수는 작은 수의 약수 중에만 존재할 수 있기 때문입니다. 따라서, 작은 수의 약수들만 검사하면 됩니다.

 

이 경우, 10과 15의 공통된 약수는 1과 5입니다. 따라서 최대공약수는 5입니다.

최대공약수만 구하기

public static void main(String[] args) {
    int n = 10;
    int m = 15;

    int minNum = Math.min(n, m);

    for (int i = minNum; i >= 1; i--) {
        if (n % i == 0 && m % i == 0) {
            System.out.println("최대공약수 : " + i);
            break;
        }
    }
}

위 코드는 n과 m의 최대공약수를 구하는 방법입니다.

여기서 minNum부터 1까지 반복하면서 n과 m 모두 나누어떨어지는 첫 번째 숫자를 찾으면 그것이 최대공약수가 됩니다.

 

 

재귀함수로 최대공약수(GCD) 구하기

아직 재귀함수를 모르신다면 재귀함수를 공부하고 보시는 것을 추천합니다.

public static void main(String[] args) {
    int n = 10;
    int m = 15;

    System.out.println(gcd(n,m));
}

public static int gcd(int n, int m) {
    if (m == 0) {
        return n;
    }

    return gcd(m, n % m);
}

 

코드 설명

1. 기본 조건 확인: gcd 메소드에서는 먼저 m이 0인지 확인합니다. 만약 m이 0이라면 n을 반환합니다. 이것은 최대공약수가 n임을 의미합니다.
2. 재귀 호출: m이 0이 아닌 경우, gcd 메소드를 재귀적으로 호출합니다. 이때 새로운 n은 이전의 m이 되고, 새로운 m은 n % m이 됩니다.

예시: 10과 15

1. 초기 호출: gcd(10, 15)
   • m이 0이 아니므로 gcd(15, 10)를 호출합니다.
2. 첫 번째 재귀 호출: gcd(15, 10)
   • m이 0이 아니므로 gcd(10, 5)를 호출합니다.
3. 두 번째 재귀 호출: gcd(10, 5)
   • m이 0이 아니므로 gcd(5, 0)을 호출합니다.
4. 세 번째 재귀 호출: gcd(5, 0)
   • m이 0이므로 n을 반환합니다. 여기서 n은 5입니다.

 

 

더 나은 방법: 유클리드 호제법

유클리드 호제법은 두 수의 최대공약수를 빠르게 구하는 알고리즘입니다. 이 방법은 큰 수를 작은 수로 나누고, 나머지가 0이 될 때까지 반복하는 방식입니다. 재귀함수를 응용한 코드 입니다.

public static void main(String[] args) {
    int n = 10;
    int m = 20;

    System.out.println(gcd(n,m));
}

public static int gcd(int n, int m) {
    while (m != 0) {
        int tmp = n % m;
        n = m;
        m = tmp;
    }

    return n;
}

 

유클리드 호제법을 사용하면 반복문의 횟수를 줄여 더 효율적으로 최대공약수를 구할 수 있습니다.

 

 

정리

• 최대공약수(GCD)는 두 수의 공통된 약수 중 가장 큰 값입니다.
• 약수는 어떤 정수를 나누었을 때 나머지가 0이 되는 수입니다.
• 최대공약수는 반복문을 통해서도 구할 수 있지만, 재귀함수와 유클리드 호제법을 사용하면 더 효율적으로 구할 수 있습니다.
• 유클리드 호제법은 큰 수를 작은 수로 나누고, 나머지가 0이 될 때까지 반복하여 GCD를 구하는 방법입니다.