Проверить все числа в небольшом диапазоне на простоту

[qx87]

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

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

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

[Dmitriy40]

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

[grizzly]

qx87 в сообщении #1238202 писал(а):

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

Не знаю, пригодится ли, но интересно и полезно знать следующее:

рувики про вероятностный "Тест Бейли — Померанца — Селфриджа — Уогстаффа" писал(а):

Ни одно составное число, меньшее $2^{64}$ (что примерно равно $1,845\cdot 10^{19}$), не проходит тест БПСВ[5]. Таким образом, этот тест можно считать детерминированным тестом простоты для чисел, меньших указанной границы. Также пока не известно ни одно составное число, большее границы, которое проходит тест.

Насколько я понимаю, это работает очень быстро.

[atlakatl]

grizzly

(Оффтоп)

grizzly в сообщении #1238214 писал(а):

Ни одно составное число, меньшее $2^{64}$ (что примерно равно $1,845\cdot 10^{19}$), не проходит тест БПСВ

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

[grizzly]

atlakatl

(Оффтоп)

atlakatl в сообщении #1238217 писал(а):

Издержки Google-переводчика?

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

[Sonic86]

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

[grizzly]

Sonic86 в сообщении #1238236 писал(а):

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

Да ладно, какие могут проблемы у таких маленьких чисел? Или я неправильно понял намёк?

[Sonic86]

grizzly в сообщении #1238237 писал(а):

Sonic86 в сообщении #1238236 писал(а):

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

Да ладно, какие могут проблемы у таких маленьких чисел? Или я неправильно понял намёк?

Я хотел сказать, что если нам надо проверить на простоту все числа в диапазоне $[N;N+L]$ при малом $L$ и произвольном, то при $L=1$ мы получим обычную задачу проверки на простоту. $L=27$ от единицы не шибко отличается: $18$ чисел с мелочью мы отсеем, а дальше все то же самое.

[atlakatl]

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

[Sonic86]

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

[Dmitriy40]

grizzly в сообщении #1238214 писал(а):

Насколько я понимаю, это работает очень быстро.

Ради интереса проверил на PARI/GP, да, очень быстро, один интервал длиной 30 (15 нечётных чисел подряд) проверяется всего примерно 15 мкс. С решетом, с его сотней миллисекунд на интервал, несравнимо.
Думаю скорость более 50 тысяч интервалов в секунду ТС устроит.
Проверяя не 15 чисел, а лишь максимум 8, можно ещё вдвое ускорить.

[qx87]

grizzly

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