\begin{tutorial}{Наибольшее общее простое}

Из того, что для двух разных чисел на отрезке их $\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 > \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$. Но тогда:
\begin{enumerate}
\item При каждом выходе за левую границу отрезка при пересчете кратного имеем число порядка $l - 1000$, так как максимальный множитель у кратного равен $10^3$. Тогда для пересчета первого числа кратного $p$ достаточно прибавить один раз само $p$, так как оно порядка $10^6$.
\item Если ответ не будет найден в самом начале, то при подсчете первого момента попадания в безопасную зону будет за $\mathcal{O}(1)$ пропущено $\frac{10^6}{10^3}=10^3$ заведомо неподходящих чисел. После десяти таких итераций безопасная зона будет порядка $10^4$, поэтому в нее попадет порядка десяти чисел-кандидатов, среди которых найдется простое.
\end{enumerate}   

\end{tutorial}
