Продолжительность решета Эратосфена на заданном интервале

[fractalon]

Вчера на олимпиаде была эта задача, долго думали, причём втроём... так что пишу не без попыток решить.

Даны числа $L$ и $R$ $(2 \le L \le R \le {10}^{9})$. Изначально на воображаемой ленте записаны числа $L, L+1, L+2, \dots, R$. На первом ходе вычёркиваются все числа, кратные $2$. На следующем - все оставшиеся кратные $3$. На следующем - все кратные $4$ (ясно, что их уже не будет, но чисто формально...). Короче, на $k$-ом ходе вычёркиваются все числа, кратные $k+1$. На каком-то из ходов будет уничтожена вся лента. Требуется по данным $L$ и $R$ найти номер этого хода.

Математически я так понял, что ответом будет максимум из минимальных простых делителей чисел от $L$ до $R$. А вот дальше никак. Ясно, что если в интервале присутствуют простые числа, то ответом будет наибольшее из них. А если не присутствуют? И ещё, в случае $L=2$ решение задачи фактически означает поиск наибольше простого меньше $R$, что при заданных ограничениях и разумном времени работы очень подозрительно...

[worm2]

Поскольку задача по CS, то результатом должна быть просто программа, которая работает не слишком долгое время (при указанных ограничениях).
Если Вы будете применять решето Эратосфена "в лоб", то на реальных данных (например, $L=1$, $R=10^9$) программа будет слишком долго считать. Значит, нужно другое, более быстрое решение.

[fractalon]

Ну, ясное дело, это подразумевается... "Решето Эратосфена" я просто назвал чтоб тема отразила суть.
Как раз про более быстрое решение я и хочу осведомиться у форумчан.

[venco]

Ну вы уже почти всё написали. Надо прогнать блочного эратосфена с конца - либо найдёте простое число, либо, если весь диапазон закончился, сможете вычислить, на каком ходе вычеркнется последнее число. Иначе перейти к предыдущему блоку и т.д.

[Guliashik]

Вроде как между двумя простыми $\le 10^9$ зазор не превышает нескольких сотен. Поэтому проверить нам надо небольшое количество чисел на простоту за корень. В итоге должно быть быстрее чем реализация Эратосфена.

[venco]

Guliashik в сообщении #1008505 писал(а):

В итоге должно быть быстрее чем реализация Эратосфена.

Всё равно придётся эратосфена прогонять, если простого числа не найдётся, так что можно и не заморачиваться с другими тестами.

[Guliashik]

venco
Казалось бы в этом случае Эратосфен всё равно не нужен(в явном виде). За корень мы можем разложить на простые наше константное количество чисел. Пробежимся по всем разложениям и найдём максимальное простое, которое и будет ответом.

[venco]

Guliashik в сообщении #1008516 писал(а):

venco
Казалось бы в этом случае Эратосфен всё равно не нужен(в явном виде).

Что значит не нужен? Да, можно сделать по другому, и времени, возможно, хватит, но Эратосфен будет быстрее и почти так же прост.

[Guliashik]

venco
Не знаю насчёт скорости (точнее не могу понять, почему оно должно быть быстрее). По поводу памяти улучшение очевидно. С другой стороны, я даже не знаю чему равна та константа:) Просто где-то вычитал, что в районе нескольких сотен.

[venco]

В принципе я согласен, простейший вариант будет работать даже быстрее, если простое число встретится рано, и проиграет Эратосфену по времени только на больших интервалах составных чисел.
Да и ошибиться в блочном Эратосфене гораздо легче.

-- Пн апр 27, 2015 11:23:18 --

Хотя в варианте с Эратосфеном основное время потребуется на составление списка простых до $\sqrt R$. Если запросов много, то этот список можно сделать единожды, и тогда по скорости такой вариант уже ни в каких условиях не обойти.

[Vovka17]

Guliashik в сообщении #1008505 писал(а):

Вроде как между двумя простыми $\le 10^9$ зазор не превышает нескольких сотен. Поэтому проверить нам надо небольшое количество чисел на простоту за корень. В итоге должно быть быстрее чем реализация Эратосфена.

venco в сообщении #1008564 писал(а):

В принципе я согласен, простейший вариант будет работать даже быстрее, если простое число встретится рано, и проиграет Эратосфену по времени только на больших интервалах составных чисел.

Самый большой интервал между простыми числами для этой задачи равен 282 (436273009...436273291) Интервалы_между_простыми_числами.
Надо лишь проверить числа на простоту от конца($R$) к началу($L$) заданного интервала. Первое найденное простое число даст ответ на задачу.
Число чисел для проверки не превысит 282 (в худшем случае, при $R=436273290$) при любых исходных $L$ и $R$ (2 \le L \le R \le {10}^{9}).
Никакого Эратосфена здесь не надо.

[Vovka17]

Ещё забыл вариант, когда на заданном интервале не будет простых чисел...
Значит алгоритм такой:
Разлагаем числа от $Xmax=R$ до
$Xmin=\begin{cases} R-281,&\text{если $R-L\geqslant281$;}\\ L,&\text{если $R-L<281$;}\\ \end{cases} $
на простые множители.
Если встретилось простое число, то прерываем разложения и выводим ответ.
Если не встретилось, то ответ следует из максимального найденного простого делителя.
Всё!
Разложить 282 числа за выделенное программе время, думаю, несложно.

Upd: В принципе, полностью раскладывать числа на множители не требуется. Достаточно находить максимальный простой делитель для каждого числа и переходить следующему числу $X$.
(Для работы программы потребуется список простых чисел на участке от 2 до $\sqrt{10^9}=31622$ (всего будет 3502 простых). Этот список можно создать на старте программы решетом Эратосфена, например, или заложить в программу изначально, если критична скорость).

[Geen]

Используется синтаксис Javascript

// случайная генерация диапазона или просто взять из инпута
        document.getElementById('lo').value = rr[0];
        document.getElementById('hi').value = rr[1];
        while ( rr[1] >= rr[0] ) {
                var             sr = Math.sqrt(rr[1]);
                for ( var i=2; i<sr; i>2?i+=2:i++ ) {
                        if ( rr[1]%i != 0 )
                                continue;
                        sr = 0;
                        if ( document.getElementById('re').value < i )
                                document.getElementById('re').value = i;
                }
                if ( sr ) {
                        document.getElementById('re').value = rr[1];
                        break;
                }
                rr[1]--;
        }
 

Если IEшный профайлер не врёт, то порядка пары миллисекунд выполняется.