Контест Middle Производительность и кеш обновлено
Простые до 10⁸: экономное решето
Условие
Посчитайте количество простых чисел, не превосходящих n, и их сумму.
Ввод: одно число n (1 ≤ n ≤ 10⁸).
Вывод: количество простых и их сумма (сумма до 10⁸ помещается в 64-битный тип).
Ограничение по времени 2 секунды, по памяти 256 МБ. Наивная проверка каждого числа делением не уложится, а решето «в лоб» на std::vector<int> займёт 400 МБ.
Пример 1
Ввод:
10
Вывод:
4 17
Пример 2
Ввод:
1
Вывод:
0 0
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.