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

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

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

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