소수 판정과 소인수 분해

다음의 사실을 기억해두자.

어떤 수 $n$에 대한 모든 소인수는 $\sqrt n$ 이하이다. ($n$이 소수가 아니라면)

간단히 증명하자면 $a\times b=n\;(\mathrm{w.l.o.g}\; a\leq b)$에 대해 $a\leq\sqrt n\leq b$가 그 이유이다.
앞으로 이 명제를 바탕으로 모든 알고리즘을 구상할 것이다.

소수 판정
소인수 분해(미완)