[알고리즘] 최대공약수, 최소공배수, 유클리드 호제법

최대공약수(GCD)

ex) 8와 12의 최대공약수

 

더 이상 나누어 떨어지는 값이 없는 서로소 상태일 때 종료되고

나눈 값을 모두 곱하면 최대공약수가 나옵니다.

 

---

최소공배수(LCM)

ex) 8와 12의 최소공배수

 

구하려는 두 수를 곱한 값에서 최대공약수를 나누면 최소공배수가 나옵니다.

 

---

 

유클리드 호제법

최대공약수를 구하는 방법으로 구하려는 두 수를 비교해서 큰 수에서 작은 수를 0이 나올 때까지 빼나갑니다.

 

ex) 8과 12의 최대공약수