[Theory] 에라토스테네스의 체

에라토스테네스의 체

에라토스테네스의 체는 소수를 찾는 방법이다.

마치 소수를 찾는방법이 체로 거르는듯 하여 에라토스테네스의 체라는 이름이 붙었다.

알고리즘

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2. 자기자신을 제외한 2의 배수(빨강색)를 전부 지운다.
3. 자기자신을 제외한 3의 배수(초록색)를 전부 지운다.
4. 자기자신을 제외한 5의 배수(파랑색)를 전부 지운다.
5. 자기자신을 제외한 7의 배수(노란색)를 전부 지운다.
6. 위의 과정을 반복하면 원하는 임의의 숫자까지의 모든 소수가 남는다.