GCD, LCM/최대공약수, 최소공배수 구하는 법

일반적으로 정수 a, b의 최대공약수를 구한다고 하면 이런 방식으로 구할 수가 있다.

// 일반 반복문으로 구현
int gcd(int x, int y){
    int Max_Common = 0;
    for(int i = 1; i <= (x > y ? y : x); i++){ // 최대공약수이니 작은 값까지만 조사
        if(x % i == 0 && y % i == 0){ // 두 수를 i로 나눴을때 둘다 나머지가 0이면 공약수임
            Max_Common = i; // 끝까지 반복하면서 최대공약수를 갱신
        }
    }
    return Max_Common;
}

하지만 이런 방식을 사용하면 시간 복잡도는 O(n)이며 보통 알고리즘 문제를 풀 때 시간초과 당하기 좋다.

하지만 유클리드 호제법을 사용해서 O(log n)만에 최대공약수, 최소 공배수를 구할 수 있다.

코드 자체도 간단해서, 코드만 외워도 활용할 수 있기 때문에 따로 수학적인 설명은 하지 않는다.

이론적인 부분은 다른 좋은 글들이 많이 있기에 바로 활용할 수 있는 코드만 작성한다.

 

GCD(Greatest Common Divisor) - 최대공약수

// 재귀함수로 작성.
int GCD(int x, int y){
    if(y == 0) return x;
    else return GCD(y,x % y);
}

// 반복문으로 작성
int GCD(int x, int y){
    while(y != 0){
        int z = x % y;
        x = y;
        y = z;
    }
    return x;
}

두 정수 x, y의 최대공약수를 gcd(x, y)로 표기한다면
x = az와 y = bz를 만족하는 정수 a, b와 최대의 정수 z가 존재할 때 z를 gcd(x, y)라고 할 수 있다.

 

LCM(Least Common Multiple) - 최소공배수

int LCM(int x, int y){
    return x * y / GCD(x, y);
}

LCM(X, Y) = X * Y / GCD(X, Y)

최소공배수는 두 수의 곱을 최대공약수로 나누면 최소 공배수가 된다.