Простые в окне
Генератор ключей просеивает окна чисел далеко от нуля и ищет в них простые. Чтобы проверить его, нужен эталон: для каждого окна [L, R] — сколько в нём простых чисел и какой самый широкий промежуток между соседними простыми внутри окна. Промежуток — это разность двух соседних простых: между 23 и 29 он равен 6.
Вход
В первой строке число окон q (1 ≤ q ≤ 5). В каждой из следующих q строк — два целых L и R (1 ≤ L ≤ R ≤ 10¹², R − L ≤ 10⁶). Оба конца входят в окно.
Выход
Для каждого окна в отдельной строке — два числа: количество простых в окне и наибольшую разность соседних простых из этого окна. Если простых в окне меньше двух, вторым числом выведите 0.
Примеры
Пример 1
4 1 30 90 100 1 1 97 97
10 6 1 0 0 0 1 0
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 9 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Проверять каждое число окна делителями до корня — до миллиона делений на одно число, а чисел в окне миллион. Сколько это будет на пяти окнах?
2Подсказка 2
Любое составное число до 10¹² имеет простой делитель не больше 10⁶. Какие простые нужны, чтобы вычеркнуть все составные в окне, и сколько их?
3Идея
Это сегментное решето. Обычным решетом находим простые до √R ≤ 10⁶ — их 78 498. Потом для каждого окна заводим массив флагов длины R − L + 1 и каждым простым p вычёркиваем его кратные внутри окна. Что осталось — простые; по ним считаем количество и промежутки.
4Разбор
Первое кратное p в окне — ⌈L/p⌉ · p = (L + p − 1) / p · p в целых числах. Но начинать нужно не раньше p²: иначе в окне, которое захватывает маленькие числа, решето вычеркнет само простое p. Отдельно вычёркиваем единицу, если она попала в окно.
Промежутки считаем одним проходом по окну: помним позицию предыдущего простого и обновляем максимум разности. В Python удобно искать следующую единицу во флагах методом bytearray.find — он работает на C, и проход по миллиону флагов почти бесплатен. Вычёркивание тоже срезом: win[start - L :: p] = bytes(cnt).
Во втором тесте — настоящий рекорд: после простого 738 832 927 927 следующее простое отстоит на 540. Это самый широкий промежуток между простыми до 10¹² (последовательность A002386 в OEIS).
4+Решение
5Сложность
Простые до √R: O(√R log log R). На каждое окно длины w: O(w log log R + π(√R)) — вычёркивания плюс по одной проверке на каждое простое, даже если его кратных в окне нет. Память — O(√R + w). Перебор делителей стоил бы O(w√R) на окно — в сотни тысяч раз больше.
6Типичные ошибки
- Каждое число отдельно. Перебор делителей до корня для миллиона чисел около 10¹² не уложится ни в какое время.
- Решето от нуля до R. Массив на 10¹² флагов — терабайт.
- Единица и маленькие простые. В окне от 1 единица не простая, а 2, 3, 5 — простые; если начинать вычёркивание с первого кратного в окне, а не с p², они пропадут. Третий тест — окно [1, 10⁶], там должно получиться 78 498.
- Переполнение.
p * pи L + p до 10¹² не помещаются в 32 бита.