대량의 소수를 구해야 하는 경우에 사용하면 좋은 방법

[출처] https://ko.wikipedia.org/wiki/에라토스테네스의_체

[출처] https://ko.wikipedia.org/wiki/에라토스테네스의_체

알고리즘


  1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열
  2. 2는 소수이므로 오른쪽에 2를 쓴다.
  3. 자기 자신을 제외한 2의 배수를 모두 지운다.
  4. 남아있는 수 가운데 3은 소수이므로 3을 쓴다. (초록색)
  5. 자기 자신을 제외한 3의 배수를 모두 지운다.
  6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
  7. 자기 자신을 제외한 5의 배수를 모두 지운다.
  8. 남아 있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
  9. 자기 자신을 제외한 7의 배수를 모두 지운다.
  10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

<aside> 💡 그림의 겨우 11^2 > 120 이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 2,3,5,6의 배수를 지우고 남는 수는 모두 소수이다.

</aside>