Контест Middle Сложность обновлено
Сколько простых на отрезке: решето и префиксы
Условие
Дано q запросов. В каждом запросе нужно сказать, сколько простых чисел лежит на отрезке [l, r] включительно.
Ввод: в первой строке q (1 ≤ q ≤ 2500), далее q строк с парами l r (1 ≤ l ≤ r ≤ 5·10⁶).
Вывод: q строк, в каждой ответ на запрос.
Пример 1
Ввод:
3
1 10
11 20
5 5
Вывод:
4
4
1
Пример 2
Ввод:
2
1 1
2 2
Вывод:
0
1
Как подойти
Подсказки: 2
- Посчитайте простоту всех чисел один раз, а не в каждом запросе.
- Префиксная сумма по массиву «простое или нет» отвечает на запрос за O(1).
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.