에라토스테네스의 체

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

1부터 120까지의 수 중에서 소수를 구한다고 가정하자.

1은 소수가 아니므로 맨 처음에 제거한다.

소수인 2를 제외하고 2의 배수인 숫자들을 모두 제거한다.

(그림에서 연한 빨강으로 칠해진 부분)

다음으로 소수인 3을 제외하고 3의 배수인 숫자들을 모두 제거한다.

(그림에서 연한 초록으로 칠해진 부분)

:

이런 식으로 계속 제외하다보면 소수만 남게 된다.

(그림에서 자주색으로 칠해진 부분)

이를 이용하여 N까지의 소수를 쉽게 구할 수 있다.

이는 프로젝트 오일러 10번 문제를 푸는 데 큰 도움이 된다.