[수학][GCD LCM] 최대공약수와 최소공배수

[수학][GCD LCM] 최대공약수와 최소공배수

최대공약수 (GCD, Greatest Common Measure)

두 자연수의 경우 약수를 구해보면 공통된 약수를 가지고 있다.

이 중 가장 큰 약수를 최대공약수라 한다.

최대공약수를 구하는 가장 단순한 방법은 2부터 min(A, B)까지 모든 정수로 나누어 보는 방법이 있다.

int g = 1;
for(int i = 2; 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가 최대 공약수이다.

ex) GCD(24, 16) = GCD(16, 8) = GCD(8, 0) = 8

나머지 연산이 아닌 빼는 연산의 유클리드 호제법이 있다. 이는 알고리즘을 구현할 때 음수가 발생할 수 있어 주의해야 한다.

즉, 밑에 알고리즘을 예로 들었을 때 first와 second의 순서가 중요하다.

하지만 나머지 연산을 이용한 유클리드 호제법은 음수가 발생하지 않으며 (큰 수, 작은 수)가 아니라 (작은 수, 큰 수)가 들어와도 연산 후에는 뒤집히기 때문에 상관이 없다.

* 재귀함수를 사용하지 않고 구현한 유클리드 호제법

int gcd(int first, int second)
{
    while(second != 0)    {
        int r = first % second;
        first = second;
        second = r;
    }
    return first;
}

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

int gcd(int first, int second)
{
    if(!second)    return first;
    gcd(second, first % second);
}

* 세 수의 최대공약수는 마찬가지로 재귀함수를 통해 구할 수 있다.

(n개의 수의 최대공약수도 마찬가지로 계속 구할 수 있다.)

GCD(a, b, c) = gcd(gcd(a, b), c)

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

최소공배수는 두 자연수의 배수를 보면 공통되는 배수가 존재한다. 

이를 공배수라 하며 이러한 공배수들은 공배수의 최소값인 최소공배수의 배수들이다.

최소공배수는 두 수를 각각 소인수 분해 하였을 때 나온 소인수의 합집합에 해당한다.

또한 이 합집합은 두 집합을 더한 수 공집합을 제외하여 얻을 수 있는데

이는 결국 (두 수의 곱 / 최대공약수) 를 통해 얻을 수 있다.

int gcd(int first, int second)
{
    if(!second)    return first;
    gcd(second, first % second);
}
 
int lcm(int first, int second)
{
    return first * second / gcd(first, second);
}

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

https://www.acmicpc.net/problem/1850

https://www.acmicpc.net/problem/1934

https://www.acmicpc.net/problem/2609

https://www.acmicpc.net/problem/9613