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