← вернуться к уроку · Простые числа и решето

Простые на отрезках

6000 мс · 512 МБ · всё или ничего

Дано $q$ запросов. Для каждого — пары $L$ и $R$ — выведите количество простых чисел от $L$ до $R$ включительно.

В первой строке число $q$ от $1$ до $10^5$ . Во второй — $2q$ чисел: пары $L$ и $R$ подряд, $1 \le L \le R \le 2 \cdot 10^6$ .

$q$ чисел через пробел.

ввод

3
1 10 10 30 1 1

вывод

4 6 0

Решето строится один раз. Дальше по нему заводятся накопленные суммы — и любой запрос становится одним вычитанием.

Войдите, чтобы отправлять решения.