Euclidean Algorithm
유클리드 호제법이라고 알려져 있는 이 알고리즘은, 두 수의 최대 공약수를 찾아낼 수 있다. 어떤 두 자연수가 주어져 있다면, 이들을 나눌 수 있는 가장 큰 수를 최대 공약수라 한다. 만약, 이런 수가 1 이외에는 존재하지 않는다면, 이 두 수는 서로소 관계이다. 일반적으로, 최대 공약수를 찾아내는 것은, 주어진 수가 어떤 소수(Prime Number)로 구성되어 있는가를 알아냄으로 구할 수 있다. 즉, 소인수분해를 해보면 가장 확실하게 알 수 있다. 하지만, 소인수분해를 통한 방법은, 많은 시간을 소모한다는 단점이 있다. 유클리드 알고리즘은, 소인수분해를 필요로 하지 않으면서도, 빠르게 최대 공약수를 구할 수 있는 방법이다. 유클리드 알고리즘은 간단하다. 두 수 a, b가 주어졌을 때(a > b) a를 ..
더보기