[GCD 알고리즘] 최대공약수 알고리즘
GCD 알고리즘 GCD(Greatest Common Divider, 최대공약수)를 구하는 방법 중 하나로 유클리드 호제법(유클리드 알고리즘, Euclidean algorithm)이 있습니다. 유클리드 호제법은 간단합니다. a, b의 최대 공약수를 (a, b)라고 정의하면 다음과 같은 관계가 성립합니다. $$ \begin{align}(a, b) = (b, r) \newline &where, a \geq b, 0 \leq r < b\end{align} $$ 단, a, b는 정수이고, a를 b로 나눈 나머지는 r 입니다. 증명은 비교적 간단하지만, 수식이 조금 복잡할 수 있습니다. 따라서 최대한 핵심 수식만 쓰고, 나머지는 말로 풀었습니다. 증명은 다음과 같습니다. 1) $$ (a, b) = d, a = d ..
2019. 10. 18.
