Euclidean Algorithm

유클리드 호제법을 이용한 최대공약수, 최소공배수 알고리즘을 파이썬 스크립트로 알아보자. 최대공약수(GCD)란? - 두 자연수의 공통된 약수 중 가장 큰 수 최소공배수(LCM)란? - 두 자연수의 공통된 배수 중 가장 작은 수 최소공배수 = 두 자연수의 곱 / 최대공약수으로 구할 수 있다. 유클리드 호제법(Euclidean algorithm) 두 개의 자연수의 최대공약수를 찾는 방법 큰 수에서 작은 수를 빼면 최대공약수는 변하지 않는다. 따라서 둘 중 더 큰 값을 반복해서 빼면 최대공약수가 된다. ( ex. 60, 36 ⇒ 60-36=24, 36-24=12, 24-12=12, 12-12=0. 최대공약수 12) 빼기 대신 나머지를 구하다가 0이 될 때의 작은 값이 최대공약수이다. ( ex. 12, 28 ⇒ ..