Контест Middle Задачи на Kotlin обновлено
Сколько простых до N: решето Эратосфена
Условие
Для каждого запроса x выведи количество простых чисел, не превосходящих x.
Ввод. q (1 ≤ q ≤ 2000), затем q чисел x (0 ≤ x ≤ 5·10^6).
Вывод. q строк с ответами.
Как подойти
Подсказки: 2
- Посчитай решето один раз до максимального x.
- Префиксные суммы по признаку «простое».
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.