[알고리즘] 최대공약수, 최소공배수 Greatest common divisor, Least common multiple
개념 최대공약수(GCD)와 최소공배수(LCM)는 두 수의 공통성분으로 어떤 두 수에 대해서 두 수의 공통 최대 하한과 두 수의 공통 최소 상한을 정할 수 있는 유용한 개념입니다. 최대공약수는 두 수의 가장 큰 공통 약수를 의미하며, 최소공배수는 두 수의 가장 작은 공통 배수를 의미합니다. 예를 들어 4와 6의 최대공약수는 2이고, 최소공배수는 12입니다. $$ \begin{aligned} &4\quad=>\quad 약수(divisor)\;=\;{1,\,2,\,4}\quad 배수(multiple)\;=\;{4,\,8,\,12,\,\ldots} \\ &6\quad=>\quad 약수(divisor)\;=\;{1,\,2,\,3,\,6}\quad 배수(multiple)\;=\;{6,\,12,\,\ldots} \e..
2022. 5. 11.
