에라토스테네스의 채에서 어떤 수를 소수로 선택하면, 그 배수를 모두 제외하는 과정을 거치는 것을 보았습니다. 어떤 수의 배수가 가장 많을까요? 바로 2입니다. 즉, 우리가 외울 수 있을 정도의 간단한 소수를 추가해주는 정도로 에라토스테네스의 채의 속도는 크게 개선됩니다. 얼마나 개선될까요?
100만 이하의 소수를 에라토스테네스의 채로 찾게 될 경우, 맨 처음부터 찾으면 2의 배수를 제거하는 과정에서 50 만번 정도의 과정이 필요하게 됩니다. 3의 배수를 제거하는 과정에서는 약 33만번 정도가 돌게 되는데요. 2와 3만 이미 소수인 것을 체크해주더라도 83만 번의 시간을 단축할 수 있습니다.