고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수(prime number)를 찾는 방법이다.
마치 체로 치듯이 수를 걸러낸다고 하여 에라토스테네스의 체라고 부른다.
과정
1. 첫 소수인 2부터 n까지의 2의 배수들을 모두 제거한다.
2. 과정 1에서 3은 제거되지 않았으므로 3부터 n까지의 3의 배수들을 모두 제거한다.
3. 4는 과정 1에서 제거되었으므로 다음 숫자로 넘어간다.
4. 이런 과정을 n의 제곱근이하의 수까지 체크한다.
(n의 제곱근이하의 수까지 반복하는 이유는 n이 120이라고 할 때
120의 제곱근은 10.95...이고 11의 제곱은 121이기 때문에 범위에서 벗어난다.
또한 제곱으로 비교하는 이유는 11*2, 11*3, ... 등 그 전까지의 수들은 이미
에라토스테네스의 체에 의해 걸러졌기 때문이다.)