10 / 10 / 1
Регистрация: 27.06.2013
Сообщений: 151
|
||||||
1 | ||||||
Алгоритм нахождения простых чисел21.07.2013, 16:52. Показов 12963. Ответов 38
Метки нет (Все метки)
Вопросы:
1) Нужен алгоритм проверки числа (является ли число простим). Нужно чтобы алгоритм был быстрым (нужно проделать 104 операций за 0.5 сек )!!!! 2) Почему мой алгоритм проверки не всегда дает верный ответ?
0
|
21.07.2013, 16:52 | |
Ответы с готовыми решениями:
38
Алгоритм нахождения простых чисел Алгоритм нахождения простых чисел Алгоритм нахождения ПРОСТЫХ чисел в файле Программа нахождения простых чисел |
404 / 360 / 36
Регистрация: 11.10.2010
Сообщений: 1,907
|
|
21.07.2013, 18:42 | 22 |
2
|
45 / 48 / 5
Регистрация: 24.06.2013
Сообщений: 677
|
|
21.07.2013, 19:01 | 23 |
возможно имелось ввиду, но фразы "меньше 100" я не нашёл...
ну как же? Листаете до пункта "Некоторые свойства", там 11 по счёту свойство =) Добавлено через 1 минуту Я осознал свою ошибку, прошу прощения)
1
|
21.07.2013, 19:02 | 24 |
не, пингвин прав. Тут логическая игра слов с толку немного сбивает.эта фраза аналогична "всякое простое число >3 не делится на 3". И это верно, в отличие от обратного утверждения.
0
|
404 / 360 / 36
Регистрация: 11.10.2010
Сообщений: 1,907
|
|
21.07.2013, 20:53 | 26 |
0
|
21.07.2013, 20:59 | 27 |
0
|
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
|
|
22.07.2013, 05:34 | 28 |
0
|
22.07.2013, 08:34 | 29 |
Не по теме: 1 - не простое число такая оптимизация почти не заметна при тестировании чисел, скажем, от 1 до 10 000 000, выигрыш - сотые доли секунды. А вот если уменьшить количество лишних проверок, то можно скорость в разы увеличить.
0
|
404 / 360 / 36
Регистрация: 11.10.2010
Сообщений: 1,907
|
|
22.07.2013, 09:46 | 30 |
а можно же ведь использовать тест миллера-рабина да он не детерминированный зато работает быстро (за log3n), если память не изменяет то была задачка проверки на простоту чисел <264 и решалaсь она миллером-рабином
0
|
22.07.2013, 10:08 | 31 |
вероятностные алгоритмы не всегда хороши. А вообще, можно обобщить. Загадываете произвольное достаточно большое натуральное случайное число меньшее N, а я без проверки буду говорить, что оно не является простым, и с вероятностью
буду прав. А при росте N эта вероятность стремится к 1.
0
|
404 / 360 / 36
Регистрация: 11.10.2010
Сообщений: 1,907
|
|
22.07.2013, 10:14 | 32 |
Thinker, да но я не говорил что он на всех числах правильно работает но до 264 все правильно делает
Добавлено через 47 секунд и еще откуда такая вероятность? Добавлено через 2 минуты есть и более надежный недетерминированный тест BPSW
0
|
22.07.2013, 10:24 | 33 |
1
|
Higher
|
|
22.07.2013, 12:54 | 34 |
Только ваш алгоритм не сходится.
В сходящихся алгоритмах при увеличении числа раундов вероятность правильного ответа всегда повышается. Если взять тест Миллера-Рабина и подставить в него 2(logn)^2, то вероятность правильного ответа достигнет 1 (не стремится, а именно достигнет). Это, правда, не совсем доказано, но все же.
0
|
22.07.2013, 13:13 | 35 |
ну, это и так понятно, что в некоторых вероятностных алгоритмах вероятность зависит от некоторых параметров.
видите, не доказано, значит это гипотеза, проверенная на конечном наборе чисел, а натуральных чисел бесконечно, поэтому к гипотезам нужно с осторожностью относиться. а вообще, алгоритм получился со сложностью O(1), весело же
0
|
22.07.2013, 13:21 | 37 |
неужели?! так как (при использовании длинной арифметики и росте вычислительных возможностей) нет жесткого ограничения на диапазон рассматриваемых чисел, то замечание совсем не актуально.
0
|
Higher
|
|
22.07.2013, 13:22 | 38 |
Она доказана, но зависит от этой штуки. А эта штука, между прочим, является проблемой тысячелетия, и за ее доказательство/опровержение дают 1000000$.
Т.е. если тест Миллера внезапно не сработает на каком-то числе, то это означает, что для этого числа не работает гипотеза Римана. А это значит, что вы можете получить 1000000$ (так как контрпример является опровержением).
0
|
22.07.2013, 13:24 | 39 |
Не по теме: нельзя говорить, что какое-то утверждение доказано, если оно ссылается на недоказанное утверждение.
0
|
22.07.2013, 13:24 | |
22.07.2013, 13:24 | |
Помогаю со студенческими работами здесь
39
Нахождения больших простых чисел Программа для нахождения простых чисел от 1 до 100 Написать программу нахождения первых 50 простых чисел Напишите программу нахождения всех трехзначных простых чисел Алгоритм поиска простых чисел Алгоритм отбора простых чисел Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |