알고리즘을 작성하다 보면 최대공약수나 최소공배수를 구해야 할 때가 있습니다.
최대공약수는 유클리드 호제법으로 정말 간편하게 구할 수 있습니다.
재귀함수로 작성하거나, 반복문으로 작성할 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int gcd(int a, int b){
if (b == 0)
return a;
else
gcd(b, a % b);
}
//... or,
int gcd(int a, int b){
while (b > 0)
{
int temp = a;
a = b;
b = temp%b;
}
return a;
}
그러면 두 수의 최소공배수는 어떻게 구할까요?
사실 수학적으로 두 수 m과 n이 있을 때, m * n = 최대공약수(GCD) * 최소공배수(LCM) 이 성립합니다.
따라서 유클리드 호제법을 이용해 작성한 gcd 함수로 최대공약수를 먼저 구해놓은 뒤,
위 관계식에 의하여 두 수의 곱을 최대공약수로 나누어주면 그 값이 최소공배수가 됩니다.