https://www.acmicpc.net/problem/11653

왜 2부터 N의 제곱근까지인가

개인적인 생각.

주어진 N을 두 소인수 p, q의 곱으로 나타내자.
이렇게 하는 이유는 p, q보다 작거나 같은 나머지 소인수는 소거되었다고 가정하기 때문이다.

N = p*q

sqrt(N) = sqrt(pq). 이때 p <= q라고 하자.
sqrt(N)이 p보다 크고 q보단 작다고 가정하자. 그렇다면 p <= sqrt(pq) <= q 라고 할 수 있는데, 양변 제곱시 p^2 <= p*q <= q^2 로, 소거시 p <= q라는 자명한 결과가 나온다. 이는 반대에 대해서도 성립한다.

즉, 항상 sqrt(N)은 두 소인수 중 가장 작은 소인수보다 크기 때문에, 만일 이를 소거할 경우 남는 소인수는 단 하나가 된다. 그렇기에 가장 작은 소수 2부터 sqrt(N)까지 진행하는 것이다.