[알고리즘] | 최대공약수와 최소공배수

최대공약수

두 수 A와 B의 최대공약수 G는 A와 B의 공통된 약수 중에서 가장 큰 정수이다.

• 최대공약수를 간단히 줄여 GCD라고 한다.

[일반적인 최대공약수를 구하는 방법]

• 최대공약수를 구하는 가장 쉬운 방법은 2부터 min(A,B)까지 모든 정수로 나누어보는 방법이다.
• 이때 걸리는 시간복잡도는 O(N)
• 최대공약수가 1인 두 수를 서로소라고 한다.

int g = 1;

for (int i = 0; i < min(a, b); i++) {
    if (a % i == 0 && b % i == 0) {
        g = i;
     }
}

유클리드 호제법(Euclidean algorithm)

위에서 말한 일반적으로 최대공약수를 구하는 방법보다 더 빠르게 최대공약수를 구하는 알고리즘

• a를 b로 나눈 나머지를 r이라고 한다.
• GCD(a,b) = GCD(b,r)과 같다.
• r이 0이면 그 때 b가 최대 공약수이다.
• GCD(24,16) = GCD(16,8) = GCD(8,0) = 8

재귀함수를 이용한 유클리드 호제법

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

    return gcd(b, a % b);
}

반복문을 이용한 유클리드 호제법

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

여러수의 최대공약수를 구하는 방법

• 세 수의 최대공약수를 구하는 방법
  • GCD(a,b,c) = GCD(GCD(a,b),c)
• 네 수, N개의 숫자도 위와 같은 식으로 구할 수 있다.
  • GCD(a,b,c,d) = GCD(GCD(GCD(a,b),c),d)

최소 공배수

두 수의 최소공배수는 두 수의 배수 중에서 가장 작은 정수

• 최소공배수는 줄여서 LCM이라고 한다.
• GCD를 응용해서 구할 수 있다.
• 두 수의 최대 공약수를 g라고 하면
  • 최소공배수 lcm = g (a/g) (b/g) = g (ab)

최대공약수 최소공배수 관련문제

백준 - 최대공약수와 최소공배수(2609)