Student_161
0 / 0 / 0
Регистрация: 06.04.2014
Сообщений: 17
|
|
1 | |
Нахождения больших простых чисел07.04.2014, 00:06. Просмотров 1181. Ответов 2
Метки нет Все метки)
(
Нахождения больших простых чисел. Реализовать программу на C++. спасибо за помощь
0
|
|
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
|
07.04.2014, 00:06 |
Ответы с готовыми решениями:
2
Поиск больших простых чисел Алгоритм нахождения простых чисел Алгоритм нахождения простых чисел Алгоритм нахождения простых чисел
|
ZaMaZaN4iK
Мой лучший друг-отладчик!
|
|||||||||||
07.04.2014, 05:41 | 2 | ||||||||||
![]() Решение
Student_161, а насколько больших? Если просто простых, то Вам думаю подойдет и решето Эратосфена:
Можете погуглить в сторону решета Аткина, но оно особо сильного выигрыша не даст, хотя он и будет. Можно пойти другим путём, проверять числа на простоту. Тут уже подойдет разнообразные тесты. Простой факторизацией - это слишком долго, поэтому тесты обычно вероятностные. Лично я в олимпиадах использую всегда тест Миллера-Рабина, улучшенный со слов Гены Короткевича, который нам лекции читал.Вот код:
Также можете смотреть в сторону теста BPSW : http://e-maxx.ru/algo/bpsw
2
|
Student_161
0 / 0 / 0
Регистрация: 06.04.2014
Сообщений: 17
|
|
07.04.2014, 09:57 [ТС] | 3 |
ZaMaZaN4iK, простые числа размером не менее 512 бит
0
|
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
|
07.04.2014, 09:57 |
Методы построения простых больших чисел, теорема Поклингтона
Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |