Главная Настройка Mobile Контакты NSFW Каталог Пожертвования Купить пасскод Pics Adult Pics API Архив Реквест доски Каталог стикеров Реклама
Доски


[Ответить в тред] Ответить в тред

Check this out!


[Назад][Обновить тред][Вниз][Каталог] [ Автообновление ] 17 | 2 | 13
Назад Вниз Каталог Обновить

Почему так долго работает генератор простых чисел?? Аноним 27/06/17 Втр 19:40:50 1012691  
image.png (3Кб, 377x282)
Придумал простой и элегантный способ генерации.
Сперва все очень быстро, потом как-то тормозит.
Найти все в диапазоне до миллиона занимает около 7-8 минут.
Это медлено или норм? Сколько занимает у самых быстрых програм? Все таки миллион это дофига так то.

Аноним 27/06/17 Втр 19:45:44 1012696
Думаю проблема в алгоритме. Посоветуйся у математиков.
Аноним 27/06/17 Втр 19:59:08 1012705
А ничего, что число может не делиться на 2 и при этом быть составным?
Ответы: >>1012715
Аноним 27/06/17 Втр 20:09:04 1012715
>>1012705
А оно и не обязано делиться на два. p/2 это просто начальное значение от которого начинаем проверять и уменьшать на 1, пока не дойдем до 1 или получим в остатке 0. то есть например для 7 начинаем с 3. Работает вроде правильно
Ответы: >>1012722
Аноним 27/06/17 Втр 20:21:32 1012721
т.е. для каждого n: 1, 2, ... 10^6, ты выполняешь isPrime(n)?
для простого числa k у тебя будет k/2 проверок в цикле.
Аноним 27/06/17 Втр 20:27:41 1012722
>>1012715
>p/2 это просто начальное значение от которого начинаем проверять
тебе надо с sqrt(p) начинать, умник
ну и ты зачем-то сверху начинаешь проверять, когда надо начинать с 2 и инкрементировать (а вообще почитай про решето Эрастофена)
Аноним 27/06/17 Втр 20:34:40 1012725
Потому что надо извлекать корень из p, а не делить его на 2.
Аноним 27/06/17 Втр 20:44:12 1012733
>>1012691 (OP)
Во-первых, как уже сказали, действительно достаточно проверять числа меньше или равные sqrt(p).
Во-вторых, такой метод перебором крайне неэффективен. Для нахождения простых чисел используется маленькая теорема Ферма и вероятностный метод, построенный на ее основе. Хотя есть исключительные числа, для которых он не срабатывает (но срабатывают чуть усложненные алгоритмы), в >99% он даст верный результат
Аноним # OP  27/06/17 Втр 20:51:02 1012737
Ааааaaaaaaaaaaaaaaaa. Спасибо всем. Действительно какого хуя я на 2 делю когда надо корень извлекать. Теперь все работает мгновенно. Охуеть как я проебался.
Вместо 8 минут работает 2 секунды :DDDD
Интересно бывают в ирл такие проебы, а все думает что просто программа тормозит потому что много работы у нее, а на самом деле косяк.
А насчет алгоритмов спасибо, посмотрю. Я просто хотел чего-нить сам для начала попробовать.
Ответы: >>1012796
Аноним 28/06/17 Срд 00:08:52 1012796
>>1012737
>а все думает что просто программа тормозит потому что много работы у нее, а на самом деле косяк
Косяк называется Java
Ответы: >>1012799 >>1012879
Аноним 28/06/17 Срд 00:22:27 1012799
netormozit.png (174Кб, 421x468)
>>1012796
Ответы: >>1012879
Аноним 28/06/17 Срд 09:56:59 1012879
>>1012796
>>1012799
Чет кекнул с манек.
Аноним 28/06/17 Срд 20:28:55 1013177
Задержечку сделой, мс в 40
Аноним 13/07/17 Чтв 03:10:27 1023746
Парень играет, а публика
заводится все больше и больше
ни на одну женщину!
Ответы: >>1024152 >>1024218
Аноним 13/07/17 Чтв 10:41:41 1024054
>>1012691 (OP)
Гугли решето эратосфена.
А вообще лучше прочти CLRS, не обращая внимания на доказательства.
Аноним 13/07/17 Чтв 12:55:53 1024152
>>1023746
проиграл
Аноним 13/07/17 Чтв 14:49:36 1024218
>>1023746
нихуя не понял переведи
Аноним 14/07/17 Птн 01:28:21 1024640
>>1012691 (OP)
Переведите, что делает его прога?

[Назад][Обновить тред][Вверх][Каталог] [Реквест разбана] [Подписаться на тред] [ Автообновление ] 17 | 2 | 13
Назад Вверх Каталог Обновить

Топ тредов
Избранное
Подписывайся на официальный канал Двача в Телеграме и узнавай обо всех новостях и мемах первым! https://tlg.wtf/dvachannel[X]