Контест Middle Горутины и планировщик GMP обновлено
Подсчёт простых в диапазонах с ограничением горутин
Условие
Ответьте на q запросов: сколько простых чисел на отрезке [a, b]. Запросы обрабатываются параллельно, но одновременно работает не больше w горутин-обработчиков.
Ввод: q w (1 ≤ q ≤ 200, 1 ≤ w ≤ 16), затем q строк a b (0 ≤ a ≤ b ≤ 10⁶, суммарная длина отрезков до 5·10⁶).
Вывод: q ответов в порядке запросов.
Решение должно быть конкурентным (горутины), а вывод не должен зависеть от порядка их выполнения.
Пример
3 2
1 10
10 20
2 2
4
4
1
Как подойти
Предварительно простые до √10⁶, пул из w воркеров по каналу индексов, сегментное решето на отрезок, res[i].
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.