에라토스테네스의 체에서 제곱근 까지만 루프를 도는 이유

intro

에라토스테네스의 체로 소수를 판별하는 코드를 보면, n의 제곱근까지만 루프를 돌면서 index의 배수들을 소수목록에서 지운다. 보통 쉽게 한두줄로 왜 그런지 설명을 해놓았는데, 나는 이해가 잘 안가서 오래 생각을 해봤다.

아하! 그런거군!

자, 50까지의 수에서 2의 배수를 소수탈락 시켜보자.

2 * 2 / 2 * 3 / 2 * 4 ....... 2 * 25까지 지운다.

2의 배수만 지웠다(물론 2는 소수!)

이제 3의 배수를 지워보자.

3 * 2 / 3 * 3 / 3 * 4 / 3 * 5 ... 3 * 16까지!

3의 배수를 지웠다

4의 배수는 건너 뛰고, 5의 배수를 탈락 시켜보자!

5 * 2 / 5 * 3 / 5 * 4 / 5 * 5/ ... 5 * 10까지!

5의 배수를 지웠다

6의 배수는 건너 뛰고, 이제 7의 배수를 지워보자.

7 * 2 / 7 * 3 / 7 * 4 ... 7 * 7 까지!

그나마 49가 지워졌다

자 이제, 8의 배수를 지워보자!

8 * 2 / 8 * 3 / 8 * 4 / 8 * 5 / 8 * 6 까지,,,,음..?

이걸 뒤집어보면

2 * 8 / 3 * 8 / 4 * 8 / 5 * 8 / 6 * 8 이미 앞에서 다 했던것들이다.

8 * 7은 50을 넘어선다. 다시 말해서 50의 제곱근(7.07....)을 넘어서는 숫자가 뭔가 본인도 뭐좀 지워보겠다고 나서봤자!, 이미 앞에서 다~~지웠던 것들이거나, 이제좀 이전에 다 되어있는거를 넘어서서 뭔가 해보려고 하면, 그건 또 50을 넘는다.

다른 예를들어보면, n = 100일때, 10안쪽에 있는 숫자들만, 열심히 배수 찾아서 지우면 되고, 100의 제곱근인 10보다 큰 11은 뭐좀 해보겠다고 나서면, 어차피 2 * 11, 3 * 11 ....9 * 11이 다~ 이미 해놨고, 자기도 좀 슬슬 힘을 써보려고 10 * 11, 11 * 11... 하고 싶겠지만, 이거는 어차피 100을 넘어선다는 말이다.

결론 : n ** 0.5 까지만 루프 돌자.

Add Comment