대량의 소수를 구해야 하는 경우에 사용하면 좋은 방법
![[출처] https://ko.wikipedia.org/wiki/에라토스테네스의_체](https://s3-us-west-2.amazonaws.com/secure.notion-static.com/e616cfb0-c688-405e-9ccd-ce55ff82df97/Sieve_of_Eratosthenes_animation.gif)
[출처] https://ko.wikipedia.org/wiki/에라토스테네스의_체
알고리즘
- 2부터 소수를 구하고자 하는 구간의 모든 수를 나열
- 2는 소수이므로 오른쪽에 2를 쓴다.
- 자기 자신을 제외한 2의 배수를 모두 지운다.
- 남아있는 수 가운데 3은 소수이므로 3을 쓴다. (초록색)
- 자기 자신을 제외한 3의 배수를 모두 지운다.
- 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
- 자기 자신을 제외한 5의 배수를 모두 지운다.
- 남아 있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
- 자기 자신을 제외한 7의 배수를 모두 지운다.
- 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.
<aside>
💡 그림의 겨우 11^2 > 120 이므로 11보다 작은 수의 배수들만 지워도 충분하다.
즉, 2,3,5,6의 배수를 지우고 남는 수는 모두 소수이다.
</aside>