지우는 순서
처음에 2부터 N까지를 후보로 둔다. 남아 있는 가장 작은 후보 p를 소수로 정하고 p 자체를 제외한 그 배수들을 지운다. 다음 남은 후보로 같은 작업을 반복한다. 0과 1은 처음부터 소수 후보가 아니다.
제곱근에서 멈추는 이유
N 이하의 합성수에는 √N 이하인 소인수가 반드시 있다. 두 인수가 모두 √N보다 크면 그 곱은 N보다 커지기 때문이다. 따라서 √N 이하의 소수 배수들을 지우고 나면 남은 후보는 소수다.
배수의 시작점
p를 처리할 때 p²보다 작은 p의 배수들은 더 작은 소인수의 단계에서 이미 제외되어 있다. 따라서 p²부터 지우면 중복 처리를 줄일 수 있다. p 자체를 지우지 않는 것도 중요하다.
30까지의 예
2의 배수와 3의 배수를 지운 뒤 5의 단계에서 25를 제외하면 된다. 이후 7²>30이므로 멈춘다. 남는 수는 2, 3, 5, 7, 11, 13, 17, 19, 23, 29다. 한 수만 검사하는 문제와 범위 전체의 표를 만드는 문제는 구별한다.