быстрая генерация простых чисел #696810

Коллеги, привет. Может кто разрабатывал генераторы простых чисел? Какие есть быстрые алгоритмы, сопоставимые/более быстрые чем решето Аткина? Несколько дней назад разработал новый алгоритм генерации простых чисел, достаточно элементарный, и пока только на 1С. Но работает в 4.5 раза быстрее чем решето Аткина в реализации IamAlexy Генерирует до 15 млн. простые за 40 сек, в то время как решето Аткина в реализации IamAlexy - за 187 секунд. Мой алгорим -тоже решето, но имеет мало общего с Эратосфена, Аткина и пр. В сети описание чего-то похожего пока не обнаружил. Хочу перекодить на Java, посмотреть на больших числах, т.к. в 1С дальше 15 млн. уже нехватка памяти.

:) ты с 2009 г. не спал и не ел, все работал чтобы победить мою обработку? похвально похвально.. надеюсь ты ее скачал и запустил на своем компе а не смотрел на циферки со скриншотов?

спал и ел, работал. задачка интересная, вот и вспомнил. обработку запускал на своем компе и твою и свою. понятно, что твой код взят с википедии, он упрощен для демонстрации идеи решета Аткина. надо брать реальную реализацию и сравнивать с ней.

Вроде нет быстрее решета Аткина.

"It generates the 50847534 primes up to 1000000000 in just 8 seconds on a Pentium II-350". (Это про решето Аткина) Вот похоже, какой-то ориентир в первом приближении. Если дойду до миллиарда за сопоставимое время, можно будет прорабатывать тему более конкретно.

ну-ну...

если простые числа расположить в полярной ситеме координат - почему то прослеживается группирование.. ане равномерная размазня.. - так пишут британские учоные

Ты просто скажи какая сложность алгоритма. У Аткина N/loglogN А то может у тебя линейная, просто на первых миллионах дает хороший результат, а асимптотически фигня будет

и желательно сколько памяти тратит.

[разработал новый алгоритм генерации простых чисел] - ООО! Патентуй скорей! Это как минимум Нобелевка! Жаль только, что Нобелевку по математике не дают

Не нобелевка конечно, но если лучше чем , то в википедию впишут.

Некогда не догадывался 1С использовать для такой ерунды. Не глумитесь! 1С исключительно для зарабатывания денег!

а зачем тебе это нужно?

Это все равно, что у Колумба, отплывающего спросить "Зачем тебе это нужно?" Открыть новые алгоритмы. Назвать их своим именем. Прославиться.

новый алгоритм генерации простых чисел???? Тут конуренция поболее будет, чем если индусов пустить 1сить

Ну если так, то тогда я очень рад, тому, что нахожусь на одном форуме с таким человеком, даже не общаясь с ним.

Главное 3-й пункт, а как не самое главное. :)

Наоборот, в генерации простых чисел, кажется, уже все возможные алгоритмы открыты и ничего нового не появляется. Он еще не доказал, что его алгоритм чем то новый и чем то производительный.

мы даже не уверены, что его алгоритм правильный

ну это я и имел ввиду

Что то затих автор

времени не сильно много. переписал свой алгоритм на java, рядом для сравнения - упрощенную реализацию решета Аткина с Википедии (по сути кода-примерно то же, что и у IamAlexy на 1С: ). Все равно удалось сравнить на простых до 22 000 000. Дальше - ограничение по типу int. Алгоритм обращается на индексы массива, а значение индекса не может быть типом long (а только этот тип представляет достаточно большие числа). Надо модифицировать реализацию алгоритма. Если говорить о результате сравнения для простых до 22 млн.: - решето Аткина 936 мск, мой алгоритм 728 мск. Выводы делать преждевременно на таких числах. Так что буду копать дальше.

Ты странно пытаешься делать. Нужно не скорость измерять, а понять сложность алгоритма, и требуемую память.

Ты не туда копаешь. Сравнивать надо не конкретные времена на конкретных количествах простых, а сложность алгоритма. Если у тебя линейная сложность О(N), то Аткин может и будет вначале отставать, но через сколько то миллиардов, рано или поздно догонит и перегонит

спасибо за совет. есть ли какая-то методика оценки сложности алгоритма?

Если не можешь сам посчитать сложность, то просто хотя бы составь график времени по точкам от 1 до 22 млн. Что получается? Прямая линия, кривизна, выпукло, вогнуто. И то же самое составь такой же график для Аткина и посмотри, что приблизительно получается на бесконечности - если кривые продолжить

Если прямая линия, то считается сложность линейная O(N) У Аткина сложность O(N)/loglog(N) т.е. если глянешь график, то, чем больше N  тем Аткин эффективнее

на отрезке, который я проверял, и аткин и мой показывают линейную зависимость.

Упрощенный Аткин линейный. N/loglogN получается после усложнения, который скорее всего Asmody не делал. Если у тебя алгоритм линейный, то это как бы не очень, достижение. Линейных алгоритмов поиска простых - куча.

N/loglogN алгоритмов куча. Аткин замечателен меньшими требованиями к памяти.

так что, если один алгоритм работает в 10 раз быстрее другого при одинаковой сложности, то это и не считается достижением?

Нет, т.к. их можно выровнять проведя хорошую оптимизацию кода или собрав специальную аппаратуру, которая может быстро проводить требуемое повторяющееся в цикле вычисление. А сложность алгоритма подобными мерами не изменишь. Аткин не линейный.

Если твой алгоритм линейный, то как бы ты его не ускорил - никакой практической ценности он не представляет.

В редких случаях, когда константа намного лучше в алгоритме с худшей сложностью, он всё-таки применяется на практике. Но для этого константа должна быть реально лучше.

похоже, нужно применить какую-нибудь адекватную методику оценки сложности алгоритма, потом делать выводы. спасибо за внимание к вопросу.

для затравки

к

Вообще вот так просто взять и оценить сложность хитрого алгоритма не выйдет. Этому учат. Долго и упорно. Могу посоветовать книгу Кормена "Алгоритмы, построение и анализ"

это бесспорно, потому и написал "для затравки"

Ну вот, не произошло революции, снова и снова... Только я не понял - на что рассчитывал ТС, обогнать алгоритм Аткина, не предложив никакой нелинейной альтернативы?

тут кроме вброса ничего не произошло - даже код не выложен

Ты должен победить O(N)/loglog(N) множители-константы не считаются Например добейся O(N)/log(N)