Придумал простой и элегантный способ генерации. Сперва все очень быстро, потом как-то тормозит. Найти все в диапазоне до миллиона занимает около 7-8 минут. Это медлено или норм? Сколько занимает у самых быстрых програм? Все таки миллион это дофига так то.
Думаю проблема в алгоритме. Посоветуйся у математиков.
А ничего, что число может не делиться на 2 и при этом быть составным?
>>1012705А оно и не обязано делиться на два. p/2 это просто начальное значение от которого начинаем проверять и уменьшать на 1, пока не дойдем до 1 или получим в остатке 0. то есть например для 7 начинаем с 3. Работает вроде правильно
т.е. для каждого n: 1, 2, ... 10^6, ты выполняешь isPrime(n)?для простого числa k у тебя будет k/2 проверок в цикле.
>>1012715>p/2 это просто начальное значение от которого начинаем проверятьтебе надо с sqrt(p) начинать, умникну и ты зачем-то сверху начинаешь проверять, когда надо начинать с 2 и инкрементировать (а вообще почитай про решето Эрастофена)
Потому что надо извлекать корень из p, а не делить его на 2.
>>1012691 (OP)Во-первых, как уже сказали, действительно достаточно проверять числа меньше или равные sqrt(p).Во-вторых, такой метод перебором крайне неэффективен. Для нахождения простых чисел используется маленькая теорема Ферма и вероятностный метод, построенный на ее основе. Хотя есть исключительные числа, для которых он не срабатывает (но срабатывают чуть усложненные алгоритмы), в >99% он даст верный результат
Ааааaaaaaaaaaaaaaaaa. Спасибо всем. Действительно какого хуя я на 2 делю когда надо корень извлекать. Теперь все работает мгновенно. Охуеть как я проебался. Вместо 8 минут работает 2 секунды :DDDD Интересно бывают в ирл такие проебы, а все думает что просто программа тормозит потому что много работы у нее, а на самом деле косяк. А насчет алгоритмов спасибо, посмотрю. Я просто хотел чего-нить сам для начала попробовать.
>>1012737>а все думает что просто программа тормозит потому что много работы у нее, а на самом деле косякКосяк называется Java
>>1012796
>>1012796>>1012799Чет кекнул с манек.
Задержечку сделой, мс в 40
Парень играет, а публика заводится все больше и больше ни на одну женщину!
>>1012691 (OP)Гугли решето эратосфена.А вообще лучше прочти CLRS, не обращая внимания на доказательства.
>>1023746проиграл
>>1023746нихуя не понял переведи
>>1012691 (OP)Переведите, что делает его прога?
