Поиск простых чисел

[Droog_Andrey]

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

Сколько простых чисел между $99999999^2$ и $100000001^2$?

Гораздо интереснее найти простые между $9999^4$ и $10001^4$

Подскажу, что всего их там $217147127025$ (расчёт количества занимает менее минуты на двухъядерном атлоне).

[venco]

Droog_Andrey в сообщении #240777 писал(а):

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

Сколько простых чисел между $99999999^2$ и $100000001^2$?

Гораздо интереснее найти простые между $9999^4$ и $10001^4$

Подскажу, что всего их там $217147127025$ (расчёт количества занимает менее минуты на двухъядерном атлоне).

Ну я специально дал такой диапазон, т.к., по уверению SerjeyMinsk, его алгоритм работает для диапазонов $[(2k-1)^2,(2k+1)^2]$.

[SerjeyMinsk]

Ребята, я согласен. Ваше решето считает быстрее. Тему закрываем.

Использование в коммерческих целях алгоритма ASSA запрещено.

[Droog_Andrey]

SerjeyMinsk в сообщении #240622 писал(а):

Если Вам нужны тысячезначные числа обратитесь в институт проблем информатики и вычислительной техники, находящийся в Минске.

Да зачем. Тысячезначные нормально обсчитываются и на домашнем компе.

-- Сб сен 05, 2009 20:06:42 --

Бодигрим в сообщении #239558 писал(а):

Именно поэтому никто не использует решета для поиска больших простых чисел. Там совершенно другие алгоритмы.

Именно решето в первую очередь и используют. За исключением редких случаев, когда делители имеют специальный вид (например, для чисел Мерсенна) и брутфорс-префакторизация оказывается быстрее.

А уже потом - вероятностные тесты на простоту. И в самом конце - строгое доказательство простоты найденного числа.

[olg]

Берется любое нечётное число n. (допустим это число 9) Возводиться в квадрат (81). Применяется формула и на выходе выходит ряд простых чисел 79, 73, 71, 67, 61, 59, 53

Интересно! Значит ваша ФОРМУЛА олжна дать пересечение рядов простых чисел для 9^2 и 8^2 , а именно 61 59 53...а для проверки эффективнсти алгоритма пользуйтесь таймером. При этом закройте все проги....

[gris]

SerjeyMinsk, чего Вы обижаетесь-то? За неделю Вашу тему разогнали до 10 страниц и почти полутора тысяч просмотров. Для этого раздела вообще небывалый случай. А теперь слух о Вашем методе начнёт расползаться во все стороны. Пропиарили на славу. Теперь уже от Вас дальнейшее зависит. Готовьте аннотацию, результатырасчётов с указанием времени, сравнительные таблицы. И не только в компьютерном виде, но и в бумажном. Большие начальники любят не презентации, а красочные плакаты. Только совет - не делайте плакаты в Ворде. Лучше в Иллюстраторе или Короле. Искренне желаю Вам успехов.

[Бодигрим]

Droog_Andrey в сообщении #240830 писал(а):

:lol: :lol: :lol:Именно решето в первую очередь и используют. За исключением редких случаев, когда делители имеют специальный вид (например, для чисел Мерсенна) и брутфорс-префакторизация оказывается быстрее.А уже потом - вероятностные тесты на простоту. И в самом конце - строгое доказательство простоты найденного числа.

Насколько я понимаю, не все решето, а лишь проверку некоторого числа малых делителей?

[Droog_Andrey]

Да, не всё, но называют его именно решетом, т.к. оно отсеивает большую часть кандидатов.

[Батороев]

Droog_Andrey в сообщении #240830 писал(а):

Именно решето в первую очередь и используют. За исключением редких случаев, когда делители имеют специальный вид (например, для чисел Мерсенна) и брутфорс-префакторизация оказывается быстрее.

А уже потом - вероятностные тесты на простоту. И в самом конце - строгое доказательство простоты найденного числа.

Берут сомнения в целесообразности первоочередного использования решета при проверке больших чисел.
Как мне видится, решето можно использовать только в полном объеме до $\sqrt N$ (или в крайнем случае, в частичном - до $\sqrt [4]{2N} $ в "обоснованных случаях"), но никак не в частичном.
Ведь даже если задействовать наименьшие простые делители, то по "закону подлости" у числа $N$ обязательно окажется делитель, ненамного, но больший, и вся работа пойдет "насмарку".
Поэтому логичнее проверку было бы начинать сразу с вероятностного теста. Здесь хоть становится ясным, что если число составное, то оно либо число Кармайкла, либо псевдопростое по проверенным основаниям.
А уж потом проверять окончательно решетом.
По крайней мере, мне так кажется.

[Droog_Andrey]

Дело в том, что отсеивание решетом чисел с малыми делителями, меньшими $p$, уменьшает количество кандидатов в общем случае примерно в

$e^{\gamma}\ln p$ ($\gamma$ - постоянная Эйлера)

раз (т.е. примерно в пятьдесят раз при просеивании до $2^{40}$). Вероятностные тесты занимают намного больше времени, чем просеивание. Собственно, просеивание обычно ведётся до тех пор, пока средняя частота отсеивания кандидатов не умньшится до величины, обратной времени, затрачиваемому на вероятностный тест. И, естественно, чем шире диапазон поиска, тем глубже используется просеивание.

"Проверять окончательно" решетом нельзя, т.к. речь идёт о числах длиной порядка 100 тысяч десятичных знаков и более, здесь только специальные тесты.

См. для начала здесь: http://primes.utm.edu/prove/index.html

[Батороев]

Droog_Andrey в сообщении #240934 писал(а):

Вероятностные тесты занимают намного больше времени, чем просеивание. Собственно, просеивание обысно ведётся до тех пор, пока средняя частота отсеивания кандидатов не умньшится до величины, обратной времени, затрачиваемому на вероятностный тест. И, естественно, чем шире диапазон поиска, тем глубже используется просеивание.

Да вроде бы, вероятностные (недетерминированные) тесты специально создавались для быстрого отсева составных чисел.
Поэтому, как они могут занимать много времени?

[Droog_Andrey]

Батороев в сообщении #240939 писал(а):

Да вроде бы, вероятностные (недетерминированные) тесты специально создавались для быстрого отсева составных чисел.

Быстрого - по сравнению с универсальными алгоритмами вроде ECPP, но не по сравнению с проверкой наличия мелких делителей.

Батороев в сообщении #240939 писал(а):

Поэтому, как они могут занимать много времени?

Читайте ссылку.

[Батороев]

Droog_Andrey в сообщении #240941 писал(а):

Читайте ссылку.

Хотел услышать ответ от Вас.

К примеру, тест Миллера-Рабина.
Зачастую, тест Миллера-Рабина уже с одного-двух раундов распознает составное число.
Если же тест не распознал составное число, то чтобы принять решение перейти к последующей полноценной проверке числа достаточно вероятности $(1-\dfrac {1}{4^{10}})$(куда уж больше?), т.е. провести 10 раундов.
Требуемое в тесте возведение чисел в степень при некоторой соответствующей оптимизации (сообщение mrbus'a) - не слишком и длинная операция.

[Droog_Andrey]

А Вы в курсе, сколько компьютерного времени занимает тест Миллера по одному основанию (например, 3) для мегабитного числа?

А сколько времени занимает проверка делимости этого числа на простые, меньшие, скажем, $2^{30}$?

[Батороев]

Droog_Andrey в сообщении #240950 писал(а):

А Вы в курсе, сколько компьютерного времени занимает тест Миллера по одному основанию (например, 3) для мегабитного числа?

А сколько времени занимает проверка делимости этого числа на простые, меньшие, скажем, $2^{30}$?

Сам я такими делами не занимаюсь, но где-то читал, что тест Миллера-Рабина работает очень оперативно.
Так как вспомнить источник не могу, то отхожу от темы в сторону.

p.s. В предыдущем сообщении забыл упомянуть, что возведение в степень производится по остаткам.