2 / 2 / 1
Регистрация: 01.05.2013
Сообщений: 109
|
||||||
1 | ||||||
Эффективный алгоритм поиска простых чисел на С++02.05.2013, 11:41. Показов 13210. Ответов 94
Метки нет (Все метки)
Хотел написать функцию которая вычисляет простое число или сложное, но оно не вычисляется. Цикл который я добавил в функцию не работает. Можете подсказать почему??? Заранее спасибо.
Простое число - которое делится на 1 и на само себя, сложное число-которое делится на 1 и на само себя и на какое-то еще число, 5 -простое число, 10-сложное число. P.S. Вот программа:
0
|
02.05.2013, 11:41 | |
Ответы с готовыми решениями:
94
Алгоритм поиска простых чисел Алгоритм поиска n простых чисел Алгоритм поиска простых чисел. Реализовать алгоритм поиска простых чисел |
670 / 198 / 29
Регистрация: 10.05.2012
Сообщений: 595
|
|
02.05.2013, 23:06 | 41 |
-=ЮрА=-,Ваша последняя программа по-прежнему не работает, число 1244042141 не простое, а она говорит, что простое. 1244042141 делится на 181
0
|
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
|
|
03.05.2013, 08:42 | 43 |
Позволю себе поучаствовать в этом безобразии, т.к. делать нечего.
-=ЮрА=- ваша последняя программа ( та, которая с этим циклом ) способна искать простые числа не больше 10000 (1002). Делая так, вы хитрите. вы проверяете только делители < 100. этого недостаточно, чтобы доказать простоту того числа. Вообще, во всех ваших программмах идет последовательный перебор нечетных делителей, а это сложность O(n) для каждого проверяемого числа. Это крайне неэффективно. PS: -=ЮрА=-, зря вы так про справочники говорите, они помогают сократить время на написание программ, избегать глупых ошибок, неверных и неэффективных (в вашем случае) алгоритмов. на основе вашей неприязни к справочникам могу предположить, что и библиотеками готовых алгоритмов вы не пользуетесь, и каждый раз всё пишете сначала. Мартышкин труд.
0
|
Заблокирован
|
|
03.05.2013, 09:49 | 44 |
- я не хитрю я проверяю делители до 2^7 видимо стоит попробовать до 2^8 если бы кто-то в частности и вы
ya_noob, разбирались в математике то увидили бы что пробор от 2 до 11 позволяет рассматривать делители уже в интервале N/10 при этом не следует рассматривать все N/10 делителей, достаточно прогнать до половины разрядов N/10 (т.е до чисел квадрат которых даст порядок рассматриваемого числа) При этом надо ещё посмотреть а не лежат ли все элементарные делителе скажем в пределах 2^8. Я уже отметил до INT_MAX мой алгоритм весьма и весьма эффективен (это воочию показано на числе операций) - вот именно что если делители лежат до 2 в 8-й лучше просто их пробрать и секономить на итерациях (ведь чисел у которых делители 181 как на пост выше не так уж и много), т.е где то в 90% случаев совершив 5-10 итерайций я уже найду составное число, в то время как просев дает всегда 84 итерации на каждое число Добавлено через 1 минуту
0
|
Заблокирован
|
||||||
03.05.2013, 10:35 | 45 | |||||
Ternsip, ты ещё здесь?
Мы до сих пор разбирали мой алгоритм, верней то что на числах за INT_MAX он ещё не 100% точен, так вот давай лучше займёмся твоим(тебе даже за него + поставил ТС наивно полагая что ты действительно прав). Так вот давай поглядим что выдаст твой алгоритм на числе 2047 (делитель 23) и числе (3277 делитель 29) http://codepad.org/CMneLlht Заметь по ссілке компипаст твоего кода (никаких моих ремарок)
0
|
670 / 198 / 29
Регистрация: 10.05.2012
Сообщений: 595
|
|
03.05.2013, 10:50 | 46 |
-=ЮрА=-, повысьте точность if(witnessLow(2, n)) return false; вместо 2-ки в функции MillerRabinLow поставьте 10
0
|
Заблокирован
|
|
03.05.2013, 11:05 | 47 |
Ternsip, я не хочу ничего повышать, я также мог сказать повысь точность пробора написав вместо 100 256, твой код уже лажает в первых 500 числах, если я повышу точность в твоём коде то в столько же раз упадёт его производительность. Разговор шёл о том что я якобы толкаю туфту юзерам, так вот туфту впарил ты бедолаге ТС.
Добавлено через 6 минут
0
|
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
|
||||||
03.05.2013, 11:14 | 48 | |||||
Проверяете число n порядка 1015 на простоту с помощью первых 100 чисел (хотя сами же выше пишете что надо искать делители среди первых sqrt( n ) чисел).
про sqrt( n ) я понимаю. как вы можете определить уровень моих познаний в математике, не спросив меня прямо об этом? Посмотрим: Вот ваша программа из 29 поста (38 - то же самое, 40 - хитрость с "i <= 100"), немного измененная для считывания из входного потока и подсчета OPCount для каждого проверяемого числа
primes.zip только архивом. там лежит список из простых чисел в txt формате Прогон программы по всем этим числам дает результат, который опровергает вашу оценку 5-10 итераций в 90 % случаев ПОДЧИСТУЮ. что вы на это скажете?
0
|
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
|
|
03.05.2013, 11:35 | 49 |
да тут я тут, просто отвлекся немного
Добавлено через 14 минут Чтобы не быть голословным и не утруждать вас я прогнал программу для тех чисел и получил 1,8 миллиардов итераций. Прикинем, что получается: пусть все составные числа проверяются за 1 итерацию, тогда на проверку миллиона чисел приходится ~1,8 миллиардов итераций с хвостиком. следовательно в среднем 1.8 * 109 / 106 = ~1800 итераций на проверку одного числа. 5-10 итераций тут и рядом не стояли Добавлено через 4 минуты ох, маленько неточно выразился. может быть и верно, что в 90 % случаев 5-10 итераций, но в оставшихся 10% случаях 22000 итераций на проверку. разительное отличие, которое игнорировать нельзя
0
|
Заблокирован
|
|
03.05.2013, 11:47 | 50 |
- я сказал это
- я проверю, - у меня стоит в последней версии 100 я сейчас поставлю 256 - ты ввёл ? По поводу простых чисел из архива - я недоверяю непроверенным данным. Если и возьму в работу тот архив то только зная код который его создал либо источник.
0
|
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
|
|
03.05.2013, 12:10 | 51 |
по поводу ввода кучи чисел: в винде в cmd можно переправлять ввод вывод с помощью угловых скобок. в линухе скорее всего тоже что-то есть
по поводу непроверенных чисел из архива: по сути нет же разницы простые они или нет, просто для этого набора чисел количество итераций больше миллиарда. а то, что они меньше миллиона можно проверить "на глаз".
0
|
Заблокирован
|
||||||
03.05.2013, 12:12 | 52 | |||||
Чтож теперь разберём по косточкам, как я уже отметил предел пробора 2^k зависит от порядка рассматриваемых чисел, для чисел из файла (а именно с максимумом) 999983 нам достаточно прогонки до 128 для адекватной проверки Есть смысл поработать над адаптивным выбором предела для нижней и верхней границей (для этого нужны исследования процессорная мощность и главное деньги). Я согласен провести исследования за пару К зелёных, найдёшь?
0
|
Заблокирован
|
||||||
03.05.2013, 12:18 | 53 | |||||
ya_noob, вот результат работы кода который подан не как "Мартышкин труд", вот незадача
0
|
|
03.05.2013, 12:23
#56
|
Не по теме: Я бы на чьём-то месте просто закрыл рот и пошёл занялся делом...
0
|
670 / 198 / 29
Регистрация: 10.05.2012
Сообщений: 595
|
||||||
03.05.2013, 12:33 | 57 | |||||
-=ЮрА=-, ваша программа всё ещё не работает 12312449 число не простое делитель 47
Добавлено через 2 минуты -=ЮрА=-, Вот последняя версия, чтобы вопросов не возникало на счёт правильности Кликните здесь для просмотра всего текста
Добавлено через 1 минуту -=ЮрА=-, тест Миллера Рабина работает за O (log3(N))
0
|
Заблокирован
|
||||||
03.05.2013, 12:58 | 59 | |||||
Ternsip, ну слава богу ты поставил 19, а то 10-кой на интервале 1-999983 было 70 тыс ошибок. А теперь сравни отработку для моего и твоего алгоритмов для чисел из primes (я остановил на миллиарде операций, сил не стало ждать + это я ещё считаю pow(x, n) как 1 операцию а ведь это n операций)
0
|
|
03.05.2013, 13:01
Эффективный алгоритм поиска простых чисел на С++
#60
|
0
|
03.05.2013, 13:01 | |
Cоставить алгоритм поиска N простых чисел Алгоритм поиска целых простых чисел Линейный алгоритм поиска простых чисел Алгоритм поиска количества простых чисел в заданном массиве Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |