Из того, что для двух разных чисел на отрезке их $$$\operatorname{gcp}(a, b)$$$ должен равняться какому-то простому числу $$$p$$$ следует, что оба числа должны делиться на $$$p$$$. Значит, это должны быть числа кратные $$$p$$$. Все числа кратные $$$p$$$ имеют вид $$$x \cdot p$$$, где $$$x$$$ — некоторое целое положительное число. Тогда, для проверки того, что на отрезке $$$[l; r]$$$ есть два числа, которые делятся на $$$p$$$, можно просто брать первые два числа кратные $$$p$$$ на этом отрезке (если они есть). Первое число кратное $$$p$$$, назовем его $$$a$$$, которое больше или равно $$$l$$$, можно вычислить по формуле $$$a = \lceil\frac{l}{p}\rceil \cdot p$$$. Второе число кратное $$$p$$$, которое больше или равно $$$l$$$, это $$$b = a + p$$$. Разумеется, оба числа $$$a$$$ и $$$b$$$ при этом должны быть меньше или равны $$$r$$$.
Рассмотрим подробнее ограничение $$$b = a + p = \lceil\frac{l}{p}\rceil \cdot p + p \leq r$$$. Вынесем $$$p$$$ за скобки: $$$p \cdot (\lceil\frac{l}{p}\rceil + 1) \leq r$$$. Известно, что частное $$$\lceil\frac{l}{p}\rceil$$$ может принимать порядка $$$\sqrt{l}$$$ различных значений. Действительно, мы имеем $$$\sqrt{l}$$$ значений при $$$p \leq \sqrt{l}$$$, а при $$$p \gt \sqrt{l}$$$ само выражение $$$\lceil\frac{l}{p}\rceil$$$ принимает значения от $$$1$$$ до $$$\sqrt{l}$$$. Таким образом, если в неравенстве $$$p \cdot (\lceil\frac{l}{p}\rceil + 1) \leq r$$$ зафиксировать значение частного $$$\lceil\frac{l}{p}\rceil = x$$$, то останется найти самое большое простое число $$$p_x$$$ такое, что $$$\lceil\frac{l}{p_x}\rceil = x$$$ и $$$p_x \cdot (x + 1) \leq r$$$. Для этого можно просто взять самый большой $$$y$$$ такой, что $$$\lceil\frac{l}{y}\rceil = x$$$ и $$$y \cdot (x + 1) \leq r$$$, а затем поискать подходящее простое число рядом с $$$y$$$. Это будет работать быстро потому, что простые числа плотно и достаточно равномерно распределены на отрезках в заданных ограничениях. При аккуратной реализации это решение позволяло сдать задачу.
Рассмотрим теперь другое решение. Из условия $$$b \le r$$$ следует, что $$$a + p \le r$$$ или $$$a \le r - p$$$. Таким образом, для фиксированного числа $$$x$$$, не обязательно простого, определена безопасная зона $$$[l; r - x]$$$ такая, что если первое число кратное $$$x$$$ на отрезке $$$[l; r]$$$ попадает в безопасную зону, то второе число кратное $$$x$$$ гарантированно попадает в отрезок $$$[l; r]$$$.
Пусть надо проверить число $$$p$$$. Найдем его первое кратное на отрезке $$$[l; r]$$$. Если первое кратное попадает в безопасную зону, то проверяем $$$p$$$ на простоту. Иначе заметим, что первое число кратное $$$p$$$ представимо в виде $$$fm=p\cdot k$$$, для некоторого целого $$$k$$$. Тогда, следующее по убыванию число, которое надо проверить, это $$$p-1$$$. Рассмотрим число $$$(p-1)\cdot k=p\cdot k-k$$$. Тогда, либо оно является первым кратным на отрезке для $$$p-1$$$, либо выходит за левую границу отрезка. Во втором случае просто пересчитаем первое кратное, а в первом случае можно поступить так: при уменьшении $$$p$$$ на $$$1$$$ увеличим безопасную зону на $$$1$$$, а первое кратное (если не выходит за границу отрезка) уменьшим на $$$k$$$. Тогда вычислим первый момент, когда какое-то число вида $$$p-i$$$ попадет в безопасную зону. Обозначим правую границу безопасной зоны за $$$last$$$. Тогда $$$fm-k \cdot i \le last + i$$$, откуда $$$i \ge \frac{fm-last}{k+1}$$$. Это позволяет нам быстро пропускать все числа, которые не попадают в безопасную зону и заведомо не имеют хотя бы двух кратных на отрезке.
Пусть теперь дан отрезок длины хотя бы $$$10^6$$$ (для меньших длин можно использовать, например, предыдущий метод). Тогда можно считать, что все интересующие нас простые также порядка $$$10^6$$$, потому что всегда существует ответ порядка $$$\frac{10^6}{2}$$$. Первое число кратное любому числу $$$x$$$ такого порядка будет иметь вид $$$x \cdot k$$$, где $$$k \le 10^3$$$. Но тогда: