Оказывается решето Эратосфена можно зделоть за линейное время: https://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BE_%D0%AD%D1%80%D0%B0%D1%82%D0%BE%D1%81%D1%84%D0%B5%D0%BD%D0%B0#.D0.A0.D0.B5.D1.88.D0.B5.D1.82.D0.BE_.D0.AD.D1.80.D0.B0.D1.82.D0.BE.D1.81.D1.84.D0.B5.D0.BD.D0.B0_.D1.81_.D0.BB.D0.B8.D0.BD.D0.B5.D0.B9.D0.BD.D1.8B.D0.BC_.D0.B2.D1.80.D0.B5.D0.BC.D0.B5.D0.BD.D0.B5.D0.BC_.D1.80.D0.B0.D0.B1.D0.BE.D1.82.D1.8B

Из минусов:
- нельзя сэкономить память храня только по одному биту на позицию
- оверхед по памяти из-за того что хранится массив из n делителей + ln n простых чисел
- плохой кеш-хит