에라토스테네스의 체는 자연수에서 소수를 찾아내는 방법입니다. 소수란 약수가 1과 자기 자신뿐인 자연수를 말합니다. (1은 제외)
에라토스테네스의 체 알고리즘은 다음과 같습니다.
1) 1은 소수에서 제외되므로 2부터 소수인 수를 찾는다.
2) 2(P=2)가 소수이므로 2의 배수 2,4,6,8, ...를 전부 제외한다.
3) 다음 소수인 3(P=2)의 배수 3,6,9, ...를 전부 제외한다.
4) 다음 소수인 5(P=2)의 배수 5,10,15,20, ...를 전부 제외한다.
5) 이 방법을 계속해서 반복한다. (2부터 N까지의 숫자 중에서 에라토스테네스의 체로 소수를 찾을 때, P의 제곱이 N보다 커질 때까지 반복하면 된다.)