2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Продолжительность решета Эратосфена на заданном интервале
Сообщение27.04.2015, 01:30 


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

Даны числа $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$, что при заданных ограничениях и разумном времени работы очень подозрительно...

 Профиль  
                  
 
 Re: Продолжительность решета Эратосфена на заданном интервале
Сообщение27.04.2015, 08:52 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Продолжительность решета Эратосфена на заданном интервале
Сообщение27.04.2015, 11:01 


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

 Профиль  
                  
 
 Re: Продолжительность решета Эратосфена на заданном интервале
Сообщение27.04.2015, 14:01 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Продолжительность решета Эратосфена на заданном интервале
Сообщение27.04.2015, 14:29 


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

 Профиль  
                  
 
 Re: Продолжительность решета Эратосфена на заданном интервале
Сообщение27.04.2015, 15:02 
Заслуженный участник


04/05/09
4582
Guliashik в сообщении #1008505 писал(а):
В итоге должно быть быстрее чем реализация Эратосфена.
Всё равно придётся эратосфена прогонять, если простого числа не найдётся, так что можно и не заморачиваться с другими тестами.

 Профиль  
                  
 
 Re: Продолжительность решета Эратосфена на заданном интервале
Сообщение27.04.2015, 15:22 


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

 Профиль  
                  
 
 Re: Продолжительность решета Эратосфена на заданном интервале
Сообщение27.04.2015, 16:30 
Заслуженный участник


04/05/09
4582
Guliashik в сообщении #1008516 писал(а):
venco
Казалось бы в этом случае Эратосфен всё равно не нужен(в явном виде).
Что значит не нужен? Да, можно сделать по другому, и времени, возможно, хватит, но Эратосфен будет быстрее и почти так же прост.

 Профиль  
                  
 
 Re: Продолжительность решета Эратосфена на заданном интервале
Сообщение27.04.2015, 17:13 


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

 Профиль  
                  
 
 Re: Продолжительность решета Эратосфена на заданном интервале
Сообщение27.04.2015, 18:07 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Re: Продолжительность решета Эратосфена на заданном интервале
Сообщение28.04.2015, 03:53 
Аватара пользователя


10/11/12
121
Бобруйск
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}).
Никакого Эратосфена здесь не надо.

 Профиль  
                  
 
 Re: Продолжительность решета Эратосфена на заданном интервале
Сообщение28.04.2015, 10:27 
Аватара пользователя


10/11/12
121
Бобруйск
Ещё забыл вариант, когда на заданном интервале не будет простых чисел...
Значит алгоритм такой:
Разлагаем числа от $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 простых). Этот список можно создать на старте программы решетом Эратосфена, например, или заложить в программу изначально, если критична скорость).

 Профиль  
                  
 
 Re: Продолжительность решета Эратосфена на заданном интервале
Сообщение28.04.2015, 15:25 
Заслуженный участник
Аватара пользователя


01/09/13
4318
код: [ скачать ] [ спрятать ]
Используется синтаксис 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шный профайлер не врёт, то порядка пары миллисекунд выполняется.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group