둠선생 연구실

소수는 약수가 1과 자기 자신밖에 없는 수이다. 따라서 소수 판정은 2부터 n-1까지의 숫자로 나눠봄으로써 알 수 있다. 하지만 연산량을 조금 줄이기 위해서 한 가지 수학적인 사실을 이용할 수 있다. - 소수는 2부터 $\sqrt{n}$까지의 정수로 나눠보면 알 수있다. 간단하게 증명하자면, 만약 n이 1을 제외한 $\sqrt{n}$ 이하의 정수로 나누어 떨어지지 않는다고 가정하면, $\sqrt{n}$보다 큰 정수 a로 나누어 떨어진다. 하지만 a로 나누어떨어진다면 n/a로도 나누어 떨어진다는 뜻이고, ($a * \frac{n}{a} = n$ 이므로) 하지만 n/a는 $\sqrt{n}$보다 작은 정수이므로 가정에 모순이 발생한다. 따라서 1을 제외한 $\sqrt{n}$이하의 정수로 나누어떨어지지 않는다면..