최대공약수(GCD), 최소공배수(LCM)을 구하는 알고리즘

두 수를 A와 B라고 하자.

최대공약수 x 최소공배수 = A x B

즉, 최소공배수는 두 수를 곱한 후 최대공약수로 나눈 수 이다.

이를 구할 때는 주로 유클리드 호제법을 이용한다. 간단하니 한 번 외워두면 편하다.

💡 유클리드 호제법

A, B에 대해서 A를 B로 나눈 나머지를 r이라고 하면(A>B), A와 B의 최대공약수는 B와 r의 최대공약수와 같다.
이를 반복해 B를 r로 나눈 나머지 r'을 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 A와 B의 최대공약수이다.

관련 문제 - 백준 2609번: 최대공약수와 최소공배수

📍 최대공약수 구현

case 1

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

case 2

if (b == 0)
    return a;
return get_gcd(b, a % b);

📍 최소공배수 구현

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