유클리드 호제법(유클리드 알고리즘)은 두 수의 최대공약수를 구하는 알고리즘이다. 최대 공약수를 구하기 전에, 먼저 약수란 무엇인지 그 정의를 정확히 알고 갈 필요가 있다. - 약수의 정의 두 수 A, B가 모두 정수일 때, A가 B의 약수라는 말은 B = A * k(k는 정수)라는 말과 동일하다. 즉, A가 B의 약수라는 말은 정수 B가 정수 A로 나누어 떨어진다는 말이다. 위와 같은 정의를 이용하면, 그 크기가 작은 수들의 경우 단순 계산으로 손쉽게 최대공약수를 구할 수 있다. 하지만, 두 수의 크기가 커지면 커질수록 단순 계산으로 구하기가 점점 어려워진다. 유클리드 호제법을 이용하면 이러한 큰 수들의 최대공약수도 쉽게 구할 수 있다. 정수 A와 B가 있다고 하자(A > B). 유클리드 호제법에 따르면..
