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

유클리드 호제법은 두 정수의 최대공약수(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\)와..

자연수 \(N\)의 약수를 구해보자.먼저 \(i=1,2,3,4\cdots\left \lfloor \sqrt N \right \rfloor\)일 때, \(N\)을 \(i\)로 나눕니다. 만약 \(N\;mod\;i = 0\) 이라면 \(i\)는 \(N\)의 약수. $$i\;|\;N$$ \(i\)가 약수라면 \(N/i\)도 약수입니다.  $$\frac{N}{i}\;|\;N$$ 그 이유는 \(N\)의 약수들은 항상 쌍으로 존재하기 때문입니다. 예를 들어 \(12\)가 \(3\)로 나누어 떨어지면 \(3\)도 \(12\)의 약수이고, \(\frac{12}{3}\)도 \(N\)의 약수입니다. 이 두 약수는 곱해서 \(12\)이 됩니다. $$ i\times \frac{N}{i} = N $$ 범위가 \(\left \l..