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

[mag_spb]

берется число по модулю 30, а результат проверяется на простоту

[Бодигрим]

Сэр, я не сходя с места могу привести с десяток вариантов того, как можно "проверять результат на простоту". Простите, играть в мыслечтение у меня нет ни малейшего желания.

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

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

[mag_spb]

Подскажите ссылку на список простых чисел до 2^31

[Droog_Andrey]

Вот такой список в "сокращённом" варианте:
http://www.primefan.ru/stuff/primes/primes.dbb

А именно: возьмите число $1$ и добавляйте к нему удвоенное значение очередного байта из файла. Таким образом Вы получите последовательно все нечётные простые числа от $3$ до $2^{31}-1$.

Этим списком удобно пользоваться при написании программ, оперирующих небольшими простыми числами, если лень писать генерирующее решето.

[maxal]

mag_spb в сообщении #279251 писал(а):

Подскажите ссылку на список простых чисел до 2^31

Вот здесь до $10^{10}$: http://www.prime-numbers.org/
А вообще такой список легко составить самому - в современных мат.пакетах есть функции тестирования простоты чисел (или же можно воспользоваться решетом Эратосфена, если не привлекать мат.пакеты).

[mag_spb]

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

[p51x]

$2^{32582657}-1$ тестите

[VAL]

mag_spb в сообщении #279954 писал(а):

Ребята дайте для проверки пару больших чисел,проверка которых актуальна на сегодняшний день(я так понимаю знаков на 80, можно и больше)

Неправильно понимаете. Т.е. про "больше" правильно
80 знаков - это даже для факторизации посильно. А для проверки на простоту - вообще не задача.

Цитата:

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

Ну вот вам три числа:
1) 49572503159650792632749163334127192089811752380369776858688329376867843835991313984719039420933581617475371146524080444003643927399711004960347653267556006670367122696295976146795162958777936837856875888630874082626768404925817886268922645453200991457850006418304544527893530519511790494631877245294984789879628755308120939302216394200734869500562351601448489337205508146096293953968925380025921045296324087174939249064748638449547053533492259021974677466165469833825243925298594673669978348104341578269433391113845896207348445733472276835262533236881557714993026567287477429245526581170912938955982784992030442830647373192127587055775796592781426107170826547502884330655559395138114244016102726247608800484718070640549903865981079562825750207290282590886975611938533537292291533122160959912352272957397873652499092342304052640684951910052292484392515055201468418203084152815795631191480479455040164451633126308098929120240150413736233496061454943003584759031025744479689901024234253688669133049449160895821373229460460956093262340310648921840853829794138922392296516986550980756682241692500014581577445273214486235932708313065557552897621743559844929724280109062594885663960411366455065919100735916128813456894393941322331945605656554584535086110525065149489681480636111714571705703654478327778971874590968179610855732300133036705912391453100718407170031944379429402742533842941486683209357091731008618018024290088586550765109149562715695697422136198905693618062426446424466566470448272759078746654912905601113091245728086665349898464899540650698244789753497600011806762010043366197947195033405986053730177404562900539034942020560412900121650674144077486304344739
2) 49572503159650792632749163334127192089811752380369776858688329376867843835991313984719039420933581617475371146524080444003643927399711004960347653267556006670367122696295976146795162958777936837856875888630874082626768404925817886268922645453200991457850006418304544527893530519511790494631877245294984789879628755308120939302216394200734869500562351601448489337205508146096293953968925380025921045296324087174939249064748638449547053533492259021974677466165469833825243925298594673669978348104341578269433391113845896207348445733472276835262533236881557714993026567287477429245526581170912938955982784992030442830647373192127587055775796592781426107170826547502884330655559395138114244016102726247608800484718070640549903865981079562825750207290282590886975611938533537292291533122160959912352272957397873652499092342304052640684951910052292484392515055201468418203084152815795631191480479455040164451633126308098929120240150413736233496061454943003584759031025744479689901024234253688669133049449160895821373229460460956093262340310648921840853829794138922392296516986550980756682241692500014581577445273214486235932708313065557552897621743559844929724280109062594885663960411366455065919100735916128813456894393941322331945605656554584535086110525065149489681480636111714571705703654478327778971874590968179610855732300133036705912391453100718407170031944379429402742533842941486683209357091731008618018024290088586550765109149562715695697422136198905693618062426446424466566470448272759078746654912905601113091245728086665349898464899540650698244789753497600011806762010043366197947195033405986053730177404562900539034942020560412900121650674144077486304347811
3) 49572503159650792632749163334127192089811752380369776858688329376867843835991313984719039420933581617475371146524080444003643927399711004960347653267556006670367122696295976146795162958777936837856875888630874082626768404925817886268922645453200991457850006418304544527893530519511790494631877245294984789879628755308120939302216394200734869500562351601448489337205508146096293953968925380025921045296324087174939249064748638449547053533492259021974677466165469833825243925298594673669978348104341578269433391113845896207348445733472276835262533236881557714993026567287477429245526581170912938955982784992030442830647373192127587055775796592781426107170826547502884330655559395138114244016102726247608800484718070640549903865981079562825750207290282590886975611938533537292291533122160959912352272957397873652499092342304052640684951910052292484392515055201468418203084152815795631191480479455040164451633126308098929120240150413736233496061454943003584759031025744479689901024234253688669133049449160895821373229460460956093262340310648921840853829794138922392296516986550980756682241692500014581577445273214486235932708313065557552897621743559844929724280109062594885663960411366455065919100735916128813456894393941322331945605656554584535086110525065149489681480636111714571705703654478327778971874590968179610855732300133036705912391453100718407170031944379429402742533842941486683209357091731008618018024290088586550765109149562715695697422136198905693618062426446424466566470448272759078746654912905601113091245728086665349898464899540650698244789753497600011806762010043366197947195033405986053730177404562900539034942020560412900121650674144077486304352147
Сколько среди них простых?
Нормальная программа должна справляться с этим вопросом быстрее чем за миллисекунду.

[Droog_Andrey]

VAL в сообщении #279969 писал(а):

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

Нормальная программа на хорошем компьютере справляется примерно за час.

[mag_spb]

Вы определитесь со временем. Сколько нужно времени для проверки этих чисел на простоту. А то я не пойму или с горя пить или от радости.

[VAL]

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

VAL в сообщении #279969 писал(а):

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

Нормальная программа на хорошем компьютере справляется примерно за час.

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

[Droog_Andrey]

Я имею в виду доказательство простоты.

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

[VAL]

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

Я имею в виду доказательство простоты.

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

Составное у меня определяется примерно за одну десятую секунды. А за секунду определяется простота. По комбинации двух вероятностных тестов. Но я доверяю

[venco]

VAL в сообщении #280313 писал(а):

Составное у меня определяется примерно за одну десятую секунды. А за секунду определяется простота. По комбинации двух вероятностных тестов. Но я доверяю

Вы имеете в виду два теста Миллера-Рабина? Тогда это очень мало. Или вы использовали другой тест?

[VAL]

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

VAL в сообщении #280313 писал(а):

Составное у меня определяется примерно за одну десятую секунды. А за секунду определяется простота. По комбинации двух вероятностных тестов. Но я доверяю

Вы имеете в виду два теста Миллера-Рабина? Тогда это очень мало. Или вы использовали другой тест?

Считал Maple'ом. В Help'е написано, что используется комбинация теста на сильную псевдопростоту (насколько я знаю, это и есть тест Рабина-Миллера) и один из тестов Люка.
Кроме того сообщается, что на сегодняшний день не известно ни одного составного, просочившегося сквозь это сито.