2 / 2 / 1
Регистрация: 01.05.2013
Сообщений: 109
|
||||||
1 | ||||||
Эффективный алгоритм поиска простых чисел на С++02.05.2013, 11:41. Показов 13219. Ответов 94
Метки нет (Все метки)
Хотел написать функцию которая вычисляет простое число или сложное, но оно не вычисляется. Цикл который я добавил в функцию не работает. Можете подсказать почему??? Заранее спасибо.
Простое число - которое делится на 1 и на само себя, сложное число-которое делится на 1 и на само себя и на какое-то еще число, 5 -простое число, 10-сложное число. P.S. Вот программа:
0
|
02.05.2013, 11:41 | |
Ответы с готовыми решениями:
94
Алгоритм поиска простых чисел Алгоритм поиска n простых чисел Алгоритм поиска простых чисел. Реализовать алгоритм поиска простых чисел |
Заблокирован
|
||||||
03.05.2013, 13:08 | 61 | |||||
- ещё раз поставишь число с пределом выше INT_MAX в алгоритм где идёт int и long - пеняй на себя, два раза предупреждать не буду. Ты лучше автору темы скажи что до последнего кода у тебя шла полная лажа даже на числах меньших 50000
На исследуй
1
|
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
|
|
03.05.2013, 13:14 | 62 |
магические числа.
попробуйте прогнать тогда уж до 2 или даже до 1. Результаты будут еще круче. вы же гоняете тесты только для чисел из моего файла, которые простые. там хоть сколько можно крутить цикл хоть до 128, хоть до 1, они будут простые в любом случае.
0
|
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
|
|||||||||||
03.05.2013, 13:20 | 63 | ||||||||||
то есть как-то так:
0
|
Заблокирован
|
||||||
03.05.2013, 13:43 | 64 | |||||
- ужас
1
|
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
|
|
03.05.2013, 13:52 | 66 |
ну да, перепутал последние 2 цифры, когда писал сообщение, что это меняет?
что насчет 128? снизьте его до 1 и покажите крутые результаты работы вашей программы
0
|
Заблокирован
|
|
03.05.2013, 14:10 | 67 |
- хорошо тогда пусть до единицы будет снижено здесь
, это ведь этот код отстаиваешь
прогнал код поста 67 на числах до 2-х млн Не по теме: Да я написал админу + прошу проверить пользователей в данной теме на клонированность уж очень подозрительны некоторые включения ответчиков.
0
|
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
|
|
03.05.2013, 14:16 | 68 |
нет. с этими тестами я не знаком. я конкретно вашу программу критиковал за магические числа в основном цикле и следовательно за неадекватные значения OPCount.
c sqrt(n)
0
|
Taatshi
|
||||||
03.05.2013, 14:44
#69
|
||||||
0
|
670 / 198 / 29
Регистрация: 10.05.2012
Сообщений: 595
|
|
03.05.2013, 15:52 | 70 |
-=ЮрА=-, Напишите сюда ваш наиболее эффективный алгоритм. Простите меня за мою невнимательность, у меня не хватает времени, чтобы читать все ваши сообщения. Я хочу посмотреть на его правильность, может, даже, оценю его асимптотику. Может, я чего то не понимаю, а, может, вы сотворите чудо. Я надеюсь, что ваш последний алгоритм будет правильно выполнять поставленную задачу.
0
|
396 / 371 / 111
Регистрация: 03.02.2013
Сообщений: 1,131
|
||||||
03.05.2013, 16:00 | 71 | |||||
Ternsip,
этот известный метод достаточно эффективен?
0
|
Заблокирован
|
|
03.05.2013, 16:58 | 72 |
- очень конструктивно!Хорошо сначала теоретическое обоснование
Пусть с = 1EN причём a*b = c, тогда порядки делителей составят далее а и b поменяются местами т.е если мы хотим посмотреть делители числа достаточно пройтись по половине разрядов. При этом следует отметить что львиная доля составных чисел будут иметь делители уже на промежутке 1...9 а вот все оставшиеся будут совокупностью двух простых чисел. Т.е задача стоит в прогонке делителей числа от 1 до sqrt(N), причём нам вначале достаточно прогнать первый десяток чисел, а затем лишь смотреть нечётные числа (т.е шаг 2). Да среди нечётных будут попадаться составные и целесообразней было бы менять иногда и шаг, но в первом приближении просто хватит прогонки нечётных. В данный моент я прервусь и вернусь в тему через несколько часов, уже с кодом для сверхбольших чисел.
0
|
670 / 198 / 29
Регистрация: 10.05.2012
Сообщений: 595
|
|
03.05.2013, 17:36 | 73 |
-=ЮрА=-, напишите код, я его проверю на контесторе, я сомневаюсь в справедливости сказанного. В вашем рассуждении вы делаете ужасную ошибку, вы думаете, что через разряды, не зависимо от числа, можно проверять его на делимость....
Добавлено через 7 минут abit, 1) это решето, а не проверка одного числа на простоту 2) мы договорились не пользоваться решетом и прекальком 3) если я попрошу вас проверить число ~10^20, которое будет простым заведомо, сколько памяти и времени потребуется... Добавлено через 5 минут -=ЮрА=-, для абсолютного теста я возьму несколько больших чисел (около 10 шт) и просумирую время выполнения вашего и моего алгоритма на них, в случае, если вы сможете написать код, который работает правильно
0
|
396 / 371 / 111
Регистрация: 03.02.2013
Сообщений: 1,131
|
|
03.05.2013, 17:44 | 74 |
Ternsip,
обычно числа типа 10^20 никто не проверяет на простоту, есть эффективные методы генерации простых чисел для нужд криптографии на вскидку если без решета - я бы проверил что число >10, а затем что последняя цифра в числе - 1,3,7 или 9, потом уже искал бы делители методом перебора от 1 до sqrt(N) (N-исходное число) исключая все чётные и кратные 5 это вроде бы уже не решето? насколько это эффективно в таком виде? впринципе и то решето можно свести к подобному подходу
0
|
396 / 371 / 111
Регистрация: 03.02.2013
Сообщений: 1,131
|
|
03.05.2013, 18:00 | 76 |
без спора, мне не тягаться с алгоритмами двух умных мужиков в своей наивности и простоте, но немного подумав - этот алгоритм не гарантирует правильный ответ, а мой гарантирует
если речь пошла о вероятностных алгоритмах - можно сейчас намутить обученную нечёткую нейронную сеть или генетический алгоритм и она будет давать ответ за несколько перемножений, не зависящих от N вообще, но естестно с определённой точностью гарантии
0
|
670 / 198 / 29
Регистрация: 10.05.2012
Сообщений: 595
|
|
03.05.2013, 18:04 | 77 |
abit, вы плохо знаете тест, если взять число 2 * log(N) ^ 2 как точность, то ошибки никогда не произойдёт
http://ru.wikipedia.org/wiki/%... 0%B5%D0%BB) Но этот алгоритм не полностью доказан, тк основывается на расширенной гипотезе Римана. Но на всех обозримых числах он работает.
0
|
396 / 371 / 111
Регистрация: 03.02.2013
Сообщений: 1,131
|
|
03.05.2013, 18:11 | 78 |
Ternsip,
я помню отрывочно этот алгоритм, и даже покопался в своей библотеке, ну например число 226801 или 486737 - не простые, а тест выдаёт простоту... а это даже не очень то и большие числа, понятно, что будет на больших интервалах да просто взять из коллекции инета последовательности псевдопростых чисел - http://oeis.org/A163209 http://oeis.org/A001262 http://oeis.org/A020229 ваш метод на них не валится?
0
|
abit
|
03.05.2013, 18:24
Эффективный алгоритм поиска простых чисел на С++
#80
|
Не по теме:
0
|
03.05.2013, 18:24 | |
Cоставить алгоритм поиска N простых чисел Алгоритм поиска целых простых чисел Линейный алгоритм поиска простых чисел Алгоритм поиска количества простых чисел в заданном массиве Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |