티끌모아태산 티끌모아태산

유클리드 호제법은 두 정수의 최대공약수(Greatest common divisor: GCD)를 구하는 효율적이고 간단한 알고리즘입니다. 기원전 300년경 그리스 수학자 유클리드(Euclid)가 편찬한 유클리드 원론(기하학 원론)에서 처음 소개돼었습니다. 가장 오래된 알고리즘으로 알려져 있습니다.두 정수 \(a\)와 \(b\)가 주어졌고 \(a\)는 \(b\)보다 크다고 하겠습니다. \(\left(a, b\in \mathbb{Z}이고\;\;a \gt b\right)\). \(a\)를 \(b\)로 나누면 \(a \div b = q\)이고 이는 \(a = bq + r\) 이렇게 다시 쓸 수 있습니다. 여기서 \(q\)는 몫(quotient)이고 \(r\)은 나머지(remainder)입니다. 여기서 \(a\)와..