2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Проверить все числа в небольшом диапазоне на простоту
Сообщение04.08.2017, 05:27 
Аватара пользователя


05/11/11
91
Мне нужно программно проверить несколько небольших диапазонов чисел на простоту. Длина каждого диапазона -- 27. Диапазонов довольно много, и они неравномерно разбросаны по числовой оси, верхний предел -- примерно $2 \cdot 10^{16}$.

Первое решение, которое приходит в голову, -- двойное решето Эратосфена. Но оно работает очень долго на таких неудобных данных. А вот второе что-то не приходит никак :)

Есть какие-то другие способы проверки таких коротких отрезков больших чисел на простоту?

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


20/08/14
11072
Россия, Москва
На таких числах простые встречаются в среднем с шагом 30-35 чисел, т.е. в интервал попадёт в среднем одно-два простых.
С другой стороны, в любом интервале (ну разве кроме первого) длиной 30 чисел простых не более 8-ми.
Я бы предложил проверять эти вот возможно простые числа каким-нибудь быстрым вероятностным тестом. Возможно он будет существенно быстрее чем 10 миллионов делений (на простые для запуска решета на кусочек, их просчитать решетом заранее, это миллисекунды) для каждого интервала. Иначе - только решето для каждого интервала, это порядка 400 миллионов тактов процессора на интервал, доли секунды.

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


09/09/14
6328
qx87 в сообщении #1238202 писал(а):
Есть какие-то другие способы проверки таких коротких отрезков больших чисел на простоту?
Не знаю, пригодится ли, но интересно и полезно знать следующее:
рувики про вероятностный "Тест Бейли — Померанца — Селфриджа — Уогстаффа" писал(а):
Ни одно составное число, меньшее $2^{64}$ (что примерно равно $1,845\cdot 10^{19}$), не проходит тест БПСВ[5]. Таким образом, этот тест можно считать детерминированным тестом простоты для чисел, меньших указанной границы. Также пока не известно ни одно составное число, большее границы, которое проходит тест.
Насколько я понимаю, это работает очень быстро.

 Профиль  
                  
 
 Re: Проверить все числа в небольшом диапазоне на простоту
Сообщение04.08.2017, 09:31 
Аватара пользователя


21/09/12

1871
grizzly

(Оффтоп)

grizzly в сообщении #1238214 писал(а):
Ни одно составное число, меньшее $2^{64}$ (что примерно равно $1,845\cdot 10^{19}$), не проходит тест БПСВ
Издержки Google-переводчика? "Пройти тест" означает проверку объекта по каким-либо методом.
В данном случае следовало написать "Тест БПСВ не выдаёт ошибочных результатов для чисел меньших $2^{64}$ (что примерно равно $1,845\cdot 10^{19}$)"

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


09/09/14
6328
atlakatl

(Оффтоп)

atlakatl в сообщении #1238217 писал(а):
Издержки Google-переводчика?
Может быть, но мне кажется, что в этом смысле "пройти тест" тоже вполне употребимо; может, как жаргон (на вход подаём много чисел, на выходе не получаем никаких ненужных -- ни одно ненужное число не прошло тест). Впрочем, настаивать не буду.

 Профиль  
                  
 
 Re: Проверить все числа в небольшом диапазоне на простоту
Сообщение04.08.2017, 10:46 
Заслуженный участник


08/04/08
8556
При уменьшении длины диапазона до единицы получаем проблему проверки числа на простоту, что какбе намекает нам.
Т.е. сначала делаем маленькое решето, а потом - все, копец.

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


09/09/14
6328
Sonic86 в сообщении #1238236 писал(а):
При уменьшении длины диапазона до единицы получаем проблему проверки числа на простоту, что какбе намекает нам.
Да ладно, какие могут проблемы у таких маленьких чисел? Или я неправильно понял намёк?

 Профиль  
                  
 
 Re: Проверить все числа в небольшом диапазоне на простоту
Сообщение04.08.2017, 11:35 
Заслуженный участник


08/04/08
8556
grizzly в сообщении #1238237 писал(а):
Sonic86 в сообщении #1238236 писал(а):
При уменьшении длины диапазона до единицы получаем проблему проверки числа на простоту, что какбе намекает нам.
Да ладно, какие могут проблемы у таких маленьких чисел? Или я неправильно понял намёк?
Я хотел сказать, что если нам надо проверить на простоту все числа в диапазоне $[N;N+L]$ при малом $L$ и произвольном, то при $L=1$ мы получим обычную задачу проверки на простоту. $L=27$ от единицы не шибко отличается: $18$ чисел с мелочью мы отсеем, а дальше все то же самое.

 Профиль  
                  
 
 Re: Проверить все числа в небольшом диапазоне на простоту
Сообщение04.08.2017, 11:44 
Аватара пользователя


21/09/12

1871
grizzly
Sonic86
Как я понял. Проверяем меньшее число из диапазона на делимость на 3, 5, 7, ..., 17, 19, 23, - или вычисляем их остатки. Решетом откидываем кратные вышеуказанным числам числа из диапазона. Оставшиеся числа тупо проверяем на простоту.

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


08/04/08
8556
Ну да, я на это я намекаю.
Хотя ... вообще интересно: пусть даны 2 нечетных числа $N$ и $N+2$. Надо их проверить на простоту. Даст ли нам тот факт, что их два, хоть какую-то полезную информацию? В принципе есть $n+1$ и $n-1$ тесты на простоту. Т.е. мы можем выполнить факторизацию $N+1=(N)+1=(N+2)-1$ 1 раз, а затем для $N+2$ воспользоваться тестом Люка, а для $N$ - $n+1$-тестом (забыл название). Так действительно будет какая-то экономия. Но все равно не верится, что тут можно как-то существенно процесс ускорить :? Оба теста общие, но не самые быстрые.
А если мы возьмем числа $N$ и $N+4$, то вообще никакой такой связи между ними не знаю.

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


20/08/14
11072
Россия, Москва
grizzly в сообщении #1238214 писал(а):
Насколько я понимаю, это работает очень быстро.
Ради интереса проверил на PARI/GP, да, очень быстро, один интервал длиной 30 (15 нечётных чисел подряд) проверяется всего примерно 15 мкс. С решетом, с его сотней миллисекунд на интервал, несравнимо.
Думаю скорость более 50 тысяч интервалов в секунду ТС устроит. ;-)
Проверяя не 15 чисел, а лишь максимум 8, можно ещё вдвое ускорить.

 Профиль  
                  
 
 Re: Проверить все числа в небольшом диапазоне на простоту
Сообщение08.08.2017, 02:44 
Аватара пользователя


05/11/11
91
grizzly

Спасибо большое, сработало!
Правда, я использовал не БПСВ, а Рабина-Миллера. Он тоже, оказывается, детерминирован до известных пределов. Потребовалось лишь проверять простые основания от 2 до 23.

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

Модераторы: Модераторы Математики, Супермодераторы



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

Сейчас этот форум просматривают: talash, tolstopuz


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

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