[Algorithm] 유클리드 호제법 (Euclidean Algorithm)

유클리드 호제법 (Euclidean Algorithm)

 

• 최대공약수, 최소공배수 (GCD, LCM)
• 최대공약수 구한 뒤 두 수의 곱을 최대공약수로 나누면 최소공배수 구할 수 있음

두 자연수의 곱 = 최대공약수 * 최소공배수
∴ 최소공배수 = 두 자연수의 곱 / 최대공약수

 

• 만약 A, B라는 두 수가 있다면 최소공배수(LCM)는 아래와 같다

LCM = A*B / GCD