1 | ||||||||||||||||
Быстрая проверка натурального числа на простоту29.09.2012, 21:35. Показов 139291. Ответов 121
Метки нет (Все метки)
Часто возникает задача проверки натурального числа на простоту. При этом имеются вероятностные и детерминированные методы проверки. Здесь рассматриваются только детерминированные алгоритмы, дающие 100% ответ на вопрос о простоте.
Хорошо известно такое утверждение: если натуральное число n>1 не делится ни на одно простое число, не превосходящее , то оно простое. В связи с этим получается самый простой способ проверки на простоту алгоритм
33
|
29.09.2012, 21:35 | |
Ответы с готовыми решениями:
121
Проверка на простоту числа Проверка числа на простоту Проверка числа на простоту Проверка числа на простоту |
24 / 3 / 0
Регистрация: 28.10.2012
Сообщений: 35
|
||||||||||||||||
01.11.2012, 19:26 | 61 | |||||||||||||||
ValeryS, да, я там потом решил этот вопрос, все дело было в этом операторе:
Thinker, в общем написал алгоритм, может его стоит оптимизировать, потому что по скорости он проигрывает в 8 раз! и уже для 128 битных чисел нужно много времени. Даже для числа 265 252 859 812 191 058 636 308 479 999 999 (11*3 = 33 знака) нужно проверить 1,6 * 1016 делителей. И если скорость 2 * 109 / сек, то получаем 1,6 * 1016 / (2 * 109) = 8 * 106 сек или 92 дня. Вот собственно функции: mask[i] хранит заранее записанную маску, у которой все единицы начиная от самого левого бита и до i, или по простому - выделяем i бит слева.
0
|
01.11.2012, 19:39 [ТС] | 62 |
AEXks, ну, ваше стремление похвально, но а на что вы расчитывали, используя длинную арифметику и алгоритм проверки на простоту экспоненциальной сложности относительно количества цифр. Так и должно быть, поэтому я побаловался этим и забросил))
Вы поймите, алгоритм должен зависеть не от аппаратуры (CPU, GPU и т.д.), а от теоретической сложности, а иначе смысла не было бы во многих криптоалгоритмах
0
|
24 / 3 / 0
Регистрация: 28.10.2012
Сообщений: 35
|
|
01.11.2012, 19:43 | 63 |
так алгоритм АКС быстрее это делает?
0
|
01.11.2012, 19:45 [ТС] | 64 |
если честно, то не знаю, времени не было его проверить. но у него заявленная сложность полиномиальная относительно количества цифр, то есть обещает быть быстрым. но оять же, не настолько быстрым, чтобы какие-то криптоалгоритмы упали бы.
0
|
24 / 3 / 0
Регистрация: 28.10.2012
Сообщений: 35
|
|
01.11.2012, 20:22 | 65 |
Thinker, может попробуете тогда для CPU реализовать хотя бы?
0
|
01.11.2012, 21:03 [ТС] | 66 |
надо будет теоремы почитать с доказательствами, а иначе нет смысла алгоритм составлять. будет время, посмотрю. с другой стороны, почему его так и не реализовали, по крайней мере, не видел реализацию. это, наверное, потому что есть гипотеза (недоказанная), которая значительно ускоряет алгоритм AKS
0
|
24 / 3 / 0
Регистрация: 28.10.2012
Сообщений: 35
|
|
01.11.2012, 21:34 | 67 |
Thinker, на паскале вроде говорят есть реализация
0
|
24 / 3 / 0
Регистрация: 28.10.2012
Сообщений: 35
|
|
01.11.2012, 21:47 | 69 |
Thinker, они же не дают точный результат
0
|
24 / 3 / 0
Регистрация: 28.10.2012
Сообщений: 35
|
|
01.11.2012, 21:50 | 71 |
Thinker, а вероятностные на много быстрее?
0
|
Котовчанин
|
||||||
22.01.2014, 18:38 | 73 | |||||
Написала когда-то программку, которая, с использованием решета Эратосфена, находит все простые и возвращает самый большой простой делитель числа. Код не идеален, потому как новичок ещё я, но работает быстро.
Буду рада советам!
0
|
4165 / 1817 / 216
Регистрация: 06.10.2010
Сообщений: 4,074
|
||||||
18.07.2014, 12:07 | 74 | |||||
А ещё на AMD есть какой-то сумасшедший набор инструкций - TBM, возможно его удастся применить к этой задаче.
0
|
Master of Orion
|
||||||
18.07.2014, 12:34 | 75 | |||||
Мне кажется, простейший способ - написать прогармму с кодогенерацией, которая сгенерирует метод, который будет проверять все числа Например взять первые 100 простых чисел, и сгенерировать файлик, где
0
|
Модератор
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,521
|
|
18.07.2014, 12:48 | 76 |
если ты внимательно читал тему то заметил что это уже предлагалось
да и речь то идет не о первых 100 числах а о числах порядка 264 и выше а еще есть 100500 разных процессоров решалась задача в общем
0
|
Master of Orion
|
|
18.07.2014, 12:57 | 77 |
ValeryS, да, я видел. Но вопрос именно в кодогенерации Прочем не важно. В любом случае для достаточно больших чисел погрешность не даст нормально сказать, какое это число (double без потерь показывает лишь 15 знаков же), а для длинной арифметики слишком много всего писать надо. Вот в лиспе....
0
|
88 / 84 / 31
Регистрация: 18.11.2013
Сообщений: 390
|
|
15.06.2015, 15:03 | 78 |
а можно добавить условие в начало:
if(n%6==1 || n%6==5) return не простое else проверять по другому ну и проверять при помощи деления на числа удовлетворяющие условию Добавлено через 2 минуты переходите на java или python, на java есть BigInt, а на python всё вообще динамически расширяется
0
|
267 / 256 / 23
Регистрация: 04.04.2012
Сообщений: 546
|
|
17.06.2015, 22:55 | 79 |
0
|
88 / 84 / 31
Регистрация: 18.11.2013
Сообщений: 390
|
||||||
17.06.2015, 23:44 | 80 | |||||
Ой, извините, наоборот, там надо так:
0
|
17.06.2015, 23:44 | |
17.06.2015, 23:44 | |
Помогаю со студенческими работами здесь
80
Проверка числа на простоту Проверка числа на простоту Проверка числа на простоту Проверка числа на простоту Проверка числа на простоту Проверка числа на простоту (нужны комментарии) Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |