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

최대공약수: 공통된 약수 중 가장 큰 수

유클리드 호제법 이용

R이 0이 될 때까지

A % B = R

A = B

B = R 

반복하고 마지막 A가 최대 공약수가 된다.

 

최소공배수: 공배수 중에서 가장 작은 수

A*B/최대공약수 이용  (최소공배수 * 최대공약수 = A * B이기 때문에)

=>A*B/gcd(A, B)

 

참고 사이트

https://twpower.github.io/69-how-to-get-gcd-and-lcm