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

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

자연수 $N$의 약수를 구해보자.먼저 $i=1,2,3,4\cdots \lfloor \sqrt{N}\rfloor$일 때, $N$을 $i$로 나눕니다. 만약 $Nmodi=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..