에라토스테네스의 체

 소수가 특정한 규칙이 없다보니 구하기 힘들지만 에라토스테네스의 체를 이용하면 쉽고 간결하고 구할 수 있다.

기본 규칙은 다음과 같다.

1. 2 이상의 자연수를 오름차순으로 정렬한 배열과 소수를 담을 배열을 준비한다.(0, 1은 자연수가 아니므로)

2. 자연수 배열 맨 앞의 값을 소수 배열에 담는다.

3. 해당하는 값을 약수로 하는 모든 값을들 자연수 배열에서 제거한다.

2~3의 과정을 반복한다.