Как стать автором
Обновить
0
0
Антон Афанасьев @Icemore

Пользователь

Отправить сообщение
В ЕГЭ по информатике до сих пор приводятся куски кода на школьном алгоритмическом (правда они дублируются на нормальных языках).
Думаю, что там имелось в виду 4*10^5.
Спасибо за новогодний контест! Было весело.

Мое решение представляет собой многопоточное блочное решето Эратосфена с предподсчетом. Идея следующая — разобьем отрезок допустимых значений инпута на равные части и подсчитаем в этих точках ответ. Тогда можно искать сумму простых только в интервале от ближайшего известного числа до n (или наоборот, в зависимости от того что ближе). В блочном решете это значит что нужно обрабатывать только те блоки, которые затрагивают эту область. Простые до корня из n нам придется найти в любом случае, но это быстро.
Ну и блоки обрабатываются независимо, поэтому запустим их в нескольких потоках. На моем двухъядерном ноутбуке это давало прирост скорости примерно в полтора раза.

Сдается мне, что, возможно, выгоднее было бы убрать потоки, а на освободившиеся символы запихать побольше предподсчета, что по видимости и сделал победитель =)

Более читаемое решение: http://pastebin.com/jjkpDNin

Информация

В рейтинге
Не участвует
Откуда
Санкт-Петербург, Санкт-Петербург и область, Россия
Зарегистрирован
Активность