[Algorithm] GCD, LCM(최대공약수, 최소공배수) 구하기 (Feat. 유클리드 호제법)

유클리드 호제법

유클리드 호제법은 유클리드가 발견한 두 수의 최대공약수를 구하는 방법이다. 원래 우리가 초등학교때 배운 방법은 컴퓨터에서 실행하려고 할 때, 두 수가 커지면 비효율적으로 동작하게 된다. 따라서 유클리드 호제법을 이용해 최대공약수를 구하고 그 다음 최소공배수를 구해야한다. 

---

최대공약수

반복문을 이용해 구현한 유클리드 호제법은 다음과 같다. 

int GCD(int a, int b)
{
    while(b!=0)
    {
        int c = a % b;
        
        a = b;
        b = c;
    }
    return a;
}

---

최소공배수

두 수의 곱은 두 수의 최대공약수와 최소공배수와 같다는 수학적 성질을 이용해 최소공배수를 구한다.

 

예를 들어 10와 15의 최대공약수는 5이다. 따라서 최소공배수를 구하기 위해서 다음과 같은 식을 만족한다.

10 * 15 = 5 * LCM

LCM = 30

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