Некоторые оптимизации решета Эратосфена для ускорения работы алгоритма:

• Решето только по нечётным числам. 23 Поскольку все чётные числа, кроме 2, — составные, можно не обрабатывать чётные числа, а оперировать только нечётными. 23 Это позволит вдвое сократить объём требуемой памяти и уменьшит количество выполняемых алгоритмом операций примерно вдвое. 23
• Просеивание простыми до корня. 2 Чтобы найти все простые числа до определённого числа, достаточно выполнить просеивание только простыми, не превосходящими корня из этого числа. 2 Число операций при таком подходе заметно уменьшится. 2
• Блочное решето. 2 Нет необходимости хранить всё время весь массив. 2 Достаточно хранить только простые до корня из числа, а остальную часть массива строить поблочно, храня в текущий момент времени только один блок. 2 Объём используемой памяти сократится и уменьшится «блуждание» по памяти. 2
• Сегментация. 1 Можно заменить одно большое решето на последовательность маленьких ситечек и высевать каждое в отдельности. 1 Простые числа, найденные в процессе высевания ситечек, не нужно хранить — их можно сразу отдавать в выходной поток. 1
• Улучшение до линейного времени работы. 2 Алгоритм Эратосфена можно преобразовать в другой алгоритм, который уже будет работать за линейное время. 2