Доброго времени суток, товарищи! Сегодня будет заключающая статья про Решето Эратосфена, мы разберем оптимизацию решета - блочное решето. Напомню, что в прошлые разы мы посмотрели обычное решето и линрешето.
Как мы знаем из одной из оптимизаций стандартного решета после корня из n невычеркнутыми останутся только простые числа, то есть просеивать нам достаточно лишь простыми до корня. Исходя из этого соображения мы можем до корня из n построить обычное решето и найти те числа, которыми мы будем вычеркивать, а дальше, не храня все числа, поблочно восстанавливать постепенно, разбив все числа от 1 до n на блоки (n не обязательно конец блока), блок за блоком, обновляя только этот блок.
Асимптотика как и у обычного Эратосфена, зато по памяти мы уйдем до O(sqrt(n)+s).
На гитхабе код приведен с комментариями, которые более подробно разъясняют код.
Вкратце. Вначале мы в отдельный массив находим все простые в промежутке [1; sqrt(n)] обычным способом. Далее разбиваем ряд чисел от 1 до n на блоки по s чисел в каждом (оптимальное s = 10000), дальше находим положение каждого простого числа, до корня из n, в блоке и начинаем просеивать от этого числа (например получится блок [12233; 12293] и при просеивании 5 мы начнем отталкиваться от 12235). Затем проверяем есть ли в блоке простые (не вычеркнутые) числа и записываем их (в данном примере приведен алгоритм считающий количество простых от 1 до n, но при желании его можно переделывать как вам угодно). Если глянуть код с комментариями, я думаю, станет понятней.
Данный код был частично взят с сайта e-maxx, частично переделан и объяснён.
На самом деле на просторах интернета я совершенно не нашел этого алгоритма, кроме как на e-maxx, где он был объяснен не ахти, надеюсь у меня получилось достаточно хорошо преподнести уникальный материал. До новых встреч!