최대공약수, 최소공배수

1. 최대공약수(GCD)

두 정수 a,b의 공약수는 a의 약수이자 b의 약수인 정수이다.
최대공약수(GCD, Great Common Divisor)는 가장 큰 공약수를 말한다.

GCD(a,b,c) = GCD(GCD(a,b), c)
세 수, 그 이상 N개의 숫자의 최대공약수는 위와 같은 식으로 구할 수 있다.

2 최대공약수 구하는 방법

2.1 Brute Force

2부터 min(a,b)까지 나눠보기 (Brute Force)

int gcd = 1;
for(int i=2; i<=min(a,b); i++){
    if(a%i == 0 && b%i ==0){
        gcd = i;
        break;
    }
}

2.2 소인수 분해 (prime factorization)

두 수를 소인수분해 해서 중복되는 부분을 찾으면 최대공약수가 된다.
예를 들어 a = 192, b = 72라고 하면
$192 = 2^6 X 3$
$72 = 2^3 X 3^2$
$\therefore GCD(192,72) = 2^3 X 3 = 24$
이런 식으로 구할 수 있다.
문제는 소인수분해를 하는게 번거롭고 느리다.

2.3 유클리드 호제법(Euclidean algorithm)

a를 b로 나눈 나머지를 r이라고 했을 때 (단 a > b), GCD(a,b) = GCD(b,r)임을 이용하면 빠르게 구할 수 있다. 나머지가 0이 될 때까지 진행하면 최대공약수를 구할 수 있다.

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

재귀 함수를 사용하면 위와 같이 나타낼 수 있고 재귀 버전은 호출스택이 쌓이기 때문에 메모리를 더 사용한다.

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

반복문으로 만든 최대공약수 함수이다. 시간복잡도는 $O(log_(a+b))$이다.

3. 최소공배수

두 정수 a,b의 공배수는 a와 b 모두의 배수가 되는 정수입니다.
최소공배수(LCM, Least Common Multiple)는 가장 작은 공배수를 말한다.

LCM(a,b,c) = LCM(LCM(a,b),c)
세 수, 그 이상 N개의 숫자의 최소공배수는 위와 같은 식으로 구할 수 있다.

4. 최소공배수 구하는 방법

최소 공배수는 위에서 구한 최대공약수를 활용해 구할 수 있다.

\(LCM(a,b) = \frac{a \times b}{GCD(a,b)}\) 두 수의 곱을 최대공약수로 나눠주면 최소공배수가 된다.

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

Ref.

• 토르비욘-최대공약수(GCD)와 최소공배수(LCM)