알고리즘, 자료구조
[정수론] 유클리드 알고리즘 / 최대공약수, 최소공배수
유클리드 알고리즘 유클리드 알고리즘은 두 자연수의 최대공약수를 효과적으로 구하는 알고리즘이다. 두 자연수의 최대공약수를 알고 있다면, 두 자연수의 최소공배수도 쉽게 구할 수 있다. 두 자연수의 최대공약수를 구하는 원시적인 방법은 아래와 같다. 각각 자연수의 약수들을 전개한다. 전개된 약수 들 중 공통된 숫자들을 곱한다. 하지만 각 자연수의 약수를 구하는 작업은 굉장히 번거롭다. 프로그래밍적으로도 시간이 많이 걸리는 작업이다. 이를 간단히 해결하기 위해 두 자연수의 최대공약수를 구할때는 유클리드 알고리즘을 사용한다. 유클리드 알고리즘은 유클리드 호제법이라고도 한다. https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC..
