[알고리즘] 최대 공약수와 최소 공배수 구하기

안녕하세요. 

이번에는 최대 공약수와 최소 공배수 구하기에 대해 알아보려고 합니다.

여기서 최대 공약수란 ?

최대공약수(最大公約數, 문화어: 련속나눔셈; 영어: greatest common divisor, 약자 GCD)는 공약수 가운데 가장 큰 하나다. 다항식이나 환의 원소에 대해서도 정의할 수 있다.(위키피디아 발췌)

그럼 최소 공배수란 무엇일까요?

수론에서, 여러 개의 정수/다항식/환의 원소의 공배수(公倍數, 영어: common multiple)는 그들 모두의 배수가 되는 정수/다항식/환의 원소이다. 최소공배수(最小公倍數, 영어: least common multiple, 약자 LCM)는 음이 아닌 공배수 가운데 가장 작은 하나이다.(위키피디아 발췌)

[최대 공약수]

/* get_gcd.cpp */
int get_gcd(int a, int b)
{
    int max_div = 1;
    int range = min(a, b);
    for (int i = range; i > 1; i--) {
        if (a%i == 0 && b % i ==0)
             max_div = i;
             break;   
    }

    return max_div;
}

[최소 공배수]

/* get_lcd.cpp */
int get_lcm(int a, int b)
{
    int gcd = get_gcd(a, b);
    int lcm = gcd * (a / gcd) * (b / gcd);

    return lcm;
}