최대공약수(gcd, great common divisor)를 구하는 함수이다. 이 방법은 유클리드의 알고리즘(Euclid's algorithm으로 알려져 있다. 내용은 다음과 같다.
m과 n을 각각 양의 정수라고 하자(m이 n보다 크거나 같다). 만약 n이 0이면, 멈추고, m이 최대공약수가 된다.
그렇지 않다면, m을 n으로 나눈 나머지를 n에 저장하고, 원래 n의 값을 m에 저장한다. 이것을 n이 0이 될 때까지 반복한다.
int get_gcd(int m, int n) {
int temp;
if (m < n) {
temp = m;
m = n;
n = temp;
}
while (n > 0) {
temp = m%n;
m = n;
n = temp;
}
return m;
}
한편 두 수의 최대공약수를 구하면 최소공배수(lcm, least common multiple)도 쉽게 구할 수 있다.
m * n = gcd(m, n) * lcm(m, n) 이므로, lcm(m, n) = m * n / gcd(m, n)이다.
int get_lcm(int m, int n) {
int gcd = get_gcd(m, n);
return m * n / gcd;
}