최대 공약수(gcd), 최소 공배수(lcm)

유클리드 호제법

2개의 수의 최소 공약수를 계산할 때 큰 수(a)를 작은 수(b)로 나누고, 나머지(r)가 0이 아니면 나누었던 수(b)를 나머지(r)로 다시 나누고 나머지가 0이 될때까지 반복합니다. 반복 하다가 나머지가 0이 될때 나눈 수가 최소 공약수가 됩니다.

예를 들어 78696과 19332의 최대공약수를 구하면,

    78696 ＝ 19332×4 ＋ 1368
    19332 ＝ 1368×14 ＋ 180
     1368 ＝ 180×7 ＋ 108
      180 ＝ 108×1 + 72
      108 ＝ 72×1 ＋ 36
       72 ＝ 36×2

36이 최소 공배수입니다.

최대 공약수(gcd, greatest common divisor)

최대 공약수를 계산하는 여러가지 방법이 있겠지만 유클리드 호제법 을 사용하여 계산하는 것이 코드도 간결하고, 성능도 뛰어납니다. 아래는 a와 b의 최대공약수를 계산하는 소스코드입니다.

int gcd(int a, int b)
{ 
    return (a % b == 0 ? b : gcd(b,a%b));
}

a 를 b 로 modular 연산(나머지 연산) 한 결과가 0이면 b 를 반환하고 함수가 종료되며, 그렇지 않을 경우 나눈수(b)와 나머지(a%b)를 parameter 로 gcd function 을 재귀호출합니다.

최소 공배수(lcm, least common multiple)

a 와 b 의 최소 공배수 계산은 위에서 구한 gcd 로 계산 할수 있습니다.

a * b = 최대 공약수(gcd) * 최소 공배수(lcm)
a * b / 최대 공약수(gcd) = 최소 공배수(lcm)

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

참고 문서 - 유클리드 호제법, 최대공약수, 최소공배수