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

최대공배수(Least Common Multiple)를 구하기 위해서는 우선 최대공약수(Great Common Divisior를 구하는 법에 대해서 알 필요가 있다. 

 

1) 최대공약수 구하기

최대공약수를 구하는 법은 유클리드 호제법을 이용하면 된다.

유클리드 호제법은 a와 b의 최대공약수를 구할 때 사용이 되는데, a와 b의 최대공약수는 b와 a를 b로 나눈 나머지의 최대공약수와 같다는 공식이다.

이를 코드로 표현해보면 

int GCD(int a, int b){
    if(a % b == 0)
        return b;
    else
        return GCD(b, a % b);
}

이렇게 나타낼 수 있다. 

 

2) 최소공배수 구하기

최대공약수를 구했다면 최소공배수를 구하는 일은 식은 죽 먹기다.

마찬가지로 유클리도 호제법에 의하면 최소공배수는 두 수의 곱 나누기 두 수의 최대공약수이다.

a * b / GCD(a, b)

이것도 코드로 표현해보자면

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

이렇게 나타낼 수 있다.

 

까먹지 말고 기억하자!!!