Решето эратосфена что это такое

Решето Эратосфена

Определение. Целое положительное число называется простым, если оно имеет ровно два различных натуральных делителя — единицу и самого себя. Единица простым числом не считается.

Самая простая реализация может выглядеть так:

Время работы

Довольно легко показать, что асимптотическое время работы алгоритма хотя бы не хуже, чем \(O(n \log n)\) : даже если бы мы входили в цикл вычёркиваний для каждого числа, не проверяя его сначала на простоту, суммарно итераций было бы

\[ \sum_k \frac = \frac <2>+ \frac <3>+ \frac <4>+ \ldots + \frac = O(n \log n) \]

Здесь мы воспользовались асимптотикой гармонического ряда.

У исходного алгоритма асимптотика должна быть ещё лучше. Чтобы найти её точнее, нам понадобятся два факта про простые числа:

\[ \sum_k \frac<1> <\ln k>\frac \approx n \int \frac<1> = n \ln \ln k \Big |_2^n = O(n \log \log n) \]

Линейное решето

Основная проблема решета Эратосфена состоит в том, что некоторые числа мы будем помечать как составные несколько раз — а именно столько раз, сколько у них различных простых делителей. Чтобы достичь линейного времени работы, нам нужно придумать способ, как рассматривать все составные числа ровно один раз.

Алгоритм

Изначально массив \(d\) заполним нулями, что означает, что все числа предполагаются простыми. В ходе работы алгортима этот массив будет постепенно заполняться. Помимо этого, будем поддерживать список \(p\) всех найденных на текущий момент простых чисел.

Применения

Массив \(d\) он позволяет искать факторизацию любого числа \(k\) за время порядка размера этой факторизации:

\[ factor(k) = \ \cup factor(k / d(k)) \]

Знание факторизации всех чисел — очень полезная информация для некоторых задач. Ленейное решето интересно не своим временем работы, а именно этим массивом минимальных простых делителей.

Источник

Решето Эратосфена, попытка минимизировать память

Введение

Одним из алгоритмов для поиска простых чисел является Решето Эратосфена предложенное еще древнегреческим математиком.

Картинка из википедии:

Смысл в вычеркивании чисел кратных уже найденным простым. Остающиеся невычеркнутыми в свою очередь являются простыми. Более подробно расписано тут.

Одна из проблем при поиске решетом это объем памяти который надо выделить под фильтруемые числа. Вычеркнутые непростые удаляются уменьшая память, но изначально объем требуется большой.

Для решения используется сегментация (когда память выделяется по кускам) и другие ухищрения (см. тут).

Реализация алгоритма

Алгоритм внизу (написан на java) предполагает минимальный объем памяти — по сути для каждого найденного простого числа мы храним еще одно число — последнее зачеркнутое (наибольшее). Если я правильно оцениваю объем памяти ln(n) — число найденных простых.

Суть алгоритма:

Допустим мы имеем несколько уже найденных простых чисел отсортированных по возрастанию. (Алгоритм стартует с [2,3]). Для каждого из них храним последнее (наибольшее) зачеркнутое число. Инициализируем самими простыми числами.

Выбираем кандидата в простые например наибольшее найденное простое число +1 (в алгоритме внизу перескакиваем четные как заведомо не простые).

Кандидат сравнивается с последним зачеркнутым текущего простого. Пока текущее зачеркнутое меньше кандидата увеличиваем его на текущее простое. Если текущее зачеркнутое равно кандидату, то кандидат не простое число. Выбираем следующего кандидата.

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

Если добрались до конца списка простых чисел (то есть все зачеркнутые больше кандидата) мы нашли очередное простое число.

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

Код на java

Тот же код на питоне:

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

Возможно это очередное изобретение велосипеда. Готов выслушать замечания.

Источник

Еще раз о поиске простых чисел

В заметке обсуждаются алгоритмы решета для поиска простых чисел. Мы подробно рассмотрим классическое решето Эратосфена, особенности его реализации на популярных языках программирования, параллелизацию и оптимизацию, а затем опишем более современное и быстрое решето Аткина. Если материал о решете Эратосфена предназначен в первую очередь уберечь новичков от регулярного хождения по граблям, то алгоритм решета Аткина ранее на Хабрахабре не описывался.

На снимке — скульптура абстрактного экспрессиониста Марка Ди Суверо «Решето Эратосфена», установленная в кампусе Стэнфорского университета

Введение

Напомним, что число называется простым, если оно имеет ровно два различных делителя: единицу и самого себя. Числа, имеющие большее число делителей, называются составными. Таким образом, если мы умеем раскладывать числа на множители, то мы умеем и проверять числа на простоту. Например, как-то так:
(Здесь и далее, если не оговорено иное, приводится JavaScript-подобный псевдокод)
Время работы такого теста, очевидно, есть O(n ½ ), т. е. растет экспоненциально относительно битовой длины n. Этот тест называется проверкой перебором делителей.

Довольно неожиданно, что существует ряд способов проверить простоту числа, не находя его делителей. Если полиномиальный алгоритм разложения на множители пока остается недостижимой мечтой (на чем и основана стойкость шифрования RSA), то разработанный в 2004 году тест на простоту AKS [1] отрабатывает за полиномиальное время. С различными эффективными тестами на простоту можно ознакомиться по [2].

Если теперь нам нужно найти все простые на достаточно широком интервале, то первым побуждением, наверное, будет протестировать каждое число из интервала индивидуально. К счастью, если у нас достаточно памяти, можно использовать более быстрые (и простые) алгоритмы решета. В этой статье мы обсудим два из них: классическое решето Эратосфена, известное еще древним грекам, и решето Аткина, наиболее совершенный современный алгоритм этого семейства.

Решето Эратосфена

Древнегреческий математик Эратосфен предложил следующий алгоритм для нахождения всех простых, не превосходящих данного числа n. Возьмем массив S длины n и заполним его единицами (пометим как невычеркнутые). Теперь будем последовательно просматривать элементы S[k], начиная с k = 2. Если S[k] = 1, то заполним нулями (вычеркнем или высеем) все последующие ячейки, номера которых кратны k. В результате получим массив, в котором ячейки содержат 1 тогда и только тогда, когда номер ячейки — простое число.

Реализация примет следующий вид:

Эффективность решета Эратосфена вызвана крайней простотой внутреннего цикла: он не содержит условных переходов, а также «тяжелых» операций вроде деления и умножения.

Оценим сложность алгоритма. Первое вычеркивание требует n/2 действий, второе — n/3, третье — n/5 и т. д. По формуле Мертенса

так что для решета Эратосфена потребуется O(n log log n) операций. Потребление памяти же составит O(n).

Оптимизация и параллелизация

Первую оптимизацию решета предложил сам Эратосфен: раз из всех четных чисел простым является только 2, то давайте сэкономим половину памяти и времени и будем выписывать и высеивать только нечетные числа. Реализация такой модификации алгоритма потребует лишь косметических изменений (код).

Наращивая шаг прогрессии и количество решет (например, при шаге прогрессии 210 нам понадобится 48 решет, что сэкономит еще 4% ресурсов) параллельно росту n, удается увеличить скорость алгоритма в log log n раз.

Сегментация

Не надо делать ситечки слишком маленькими, меньше тех же O(n ½-ε ) элементов. Так вы ничего не выиграете в асимптотике потребления памяти, но из-за накладных расходов начнете все сильнее терять в производительности.

Решето Эратосфена и однострочники

На Хабрахабре ранее публиковалась большая подборка алгоритмов Эратосфена в одну строчку на разных языках программирования (однострочники №10). Интересно, что все они на самом деле решетом Эратосфена не являются и реализуют намного более медленные алгоритмы.

Дело в том, что фильтрация множества по условию (например, на Ruby) или использование генераторных списков aka list comprehensions (например, на Haskell) вызывают как раз то, избежать чего призван алгоритм решета, а именно поэлементную проверку делимости. В результате сложность алгоритма возрастает по крайней мере до (это число фильтраций), умноженного на (минимальное число элементов фильтруемого множества), где — число простых, не превосходящих n, т. е. до O(n 3/2-ε ) действий.

Однострочник на Scala ближе к алгоритму Эратосфена тем, что избегает проверки на делимость. Однако сложность построения разности множеств пропорциональна размеру большего из них, так что в результате получаются те же O(n 3/2-ε ) операций.

Вообще решето Эратосфена тяжело эффективно реализовать в рамках функциональной парадигмы неизменяемых переменных. В случае, если функциональный язык (например, OСaml) позволяет, стоит нарушить нормы и завести изменяемый массив. В [3] обсуждается, как грамотно реализовать решето Эратосфена на Haskell при помощи техники ленивых вычеркиваний.

Решето Эратосфена и PHP

Запишем алгоритм Эратосфена на PHP. Получится примерно следующее:

Для решения этих проблем достаточно выбрать более подходящий тип данных — строку!

Теперь каждый элемент занимает ровно 1 байт, а время работы уменьшилось примерно втрое. Скрипт для измерения скорости.

Решето Аткина

В 1999 году Аткин и Бернштейн предложили новый метод высеивания составных чисел, получивший название решета Аткина. Он основан на следующей теореме.

Из элементарной теории чисел следует, что все простые, большие 3, имеют вид 12k+1 (случай 1), 12k+5 (снова 1), 12k+7 (случай 2) или 12k+11 (случай 3).

Для инициализации алгоритма заполним решето S нулями. Теперь для каждой пары (x, y), где , инкрементируем значения в ячейках S[4x 2 +y 2 ], S[3x 2 +y 2 ], а также, если x > y, то и в S[3x 2 −y 2 ]. В конце вычислений номера ячеек вида 6k±1, содержащие нечетные числа, — это или простые, или делятся на квадраты простых.

В качестве заключительного этапа пройдемся по предположительно простым номерам последовательно и вычеркнем кратные их квадратам.

Из описания видно, что сложность решета Аткина пропорциональна n, а не n log log n как у алгоритма Эратосфена.

Авторская, оптимизированная реализация на Си представлена в виде primegen, упрощенная версия — в Википедии. На Хабрахабре публиковалось решето Аткина на C#.

Как и в решете Эратосфена, при помощи wheel factorization и сегментации, можно снизить асимптотическую сложность в log log n раз, а потребление памяти — до O(n ½+o(1) ).

О логарифме логарифма

На самом деле множитель log log n растет крайне. медленно. Например, log log 10 10000 ≈ 10. Поэтому с практической точки зрения его можно полагать константой, а сложность алгоритма Эратосфена — линейной. Если только поиск простых не является ключевой функцией в вашем проекте, можно использовать базовый вариант решета Эратосфена (разве что сэкономьте на четных числах) и не комплексовать по этому поводу. Однако при поиске простых на больших интервалах (от 2 32 ) игра стоит свеч, оптимизации и решето Аткина могут ощутимо повысить производительность.

P. S. В комментариях напомнили про решето Сундарама. К сожалению, оно является лишь математической диковинкой и всегда уступает либо решетам Эратосфена и Аткина, либо проверке перебором делителей.

Источник

Решето Эратосфена

Содержание

Алгоритм

Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:

Теперь все не зачеркнутые числа в списке — простые.

На практике, алгоритм можно несколько улучшить следующим образом. На шаге № 3, числа можно зачеркивать, начиная сразу с числа , потому что все составные числа меньше его уже будут зачеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда станет больше, чем . [1]

Можно показать, что сложность алгоритма составляет операций в модели вычислений RAM, или битовых операций, [2] [3] при условии вычисления и зачеркивания каждого кратного числа за время , например при использования массивов с прямым доступом.

Неограниченный, постепенный вариант

В этом варианте простые числа вычисляются последовательно, без ограничения сверху, как числа находящиеся в промежутках между составными числами, которые вычисляются для каждого простого числа p начиная с его квадрата, с шагом в p (или для нечетных простых чисел 2p ). [3] [1] Первое простое число 2 (среди возрастающих положит

Перебор делителей

Решето Эратосфена часто путают с алгоритмами, которые отфильтровывают из заданного интервала составные числа, тестируя каждое из чисел-кандидатов с помощью перебора делителей. [4]

Широко известный функциональный код Давида Тёрнера 1975 года [5] часто принимают за решето Эратосфена, [4] но на самом деле это далёкий от оптимального вариант с перебором делителей. [3]

Псевдокод

Пример для

Запишем натуральные числа начиная от 2 до 30 в ряд:

Первое число в списке, 2 — простое. Пройдём по ряду чисел, зачёркивая все числа кратные 2 (то есть каждое второе, начиная с 2 2 = 4 ):

Следующее незачеркнутое число, 3 — простое. Пройдём по ряду чисел, зачёркивая все числа кратные 3 (то есть каждое третье, начиная с 3 2 = 9 ):

Следующее незачеркнутое число, 5 — простое. Пройдём по ряду чисел, зачёркивая все числа кратные 5 (то есть каждое пятое, начиная с 5 2 = 25 ). И т. д.

Решето Эйлера

Решето Эйлера это вариант решета Эратосфена, в котором каждое составное число удаляется из списка только один раз.

Источник

Что такое решето Эратосфена

Вы будете перенаправлены на Автор24

Решето Эратосфена — это алгоритм определения всех простых чисел до заданного целого числа N, который разработал древнегреческий учёный Эратосфен Киренский.

Введение

Решетом Эратосфена назван разработанный им алгоритм, который позволяет найти все простые числа вплоть до заданного целого числа n. Как это часто бывает, в названии алгоритма заложен принцип его функционирования. Термин решето имеет в виду фильтр, который пропускает все числа кроме простых. Список всех чисел фильтруется и при этом ненужные, составные числа отсеиваются, а искомые простые числа оставляются. Метод, как гласит легенда, был назван решетом, поскольку Эратосфен использовал для записи чисел дощечку, которая была покрыта воском, и он делал отверстия там, где писал составные числа. Эта доска стала аналогом решета, через которое отсеивались только составные числа, а простые, естественно, не отсеивались. Эратосфенам была составлена таблица простых чисел вплоть до тысячи.

Алгоритм решето Эратосфена

Чтобы найти все простые числа вплоть до некоторого числа n согласно способу Эратосфена, необходимо осуществить такие действия:

Готовые работы на аналогичную тему

Рассмотрим конкретный пример выполнения этого алгоритма для n = 30. Выпишем ряд натуральных чисел от двух до тридцати:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Первым в списке стоит простое число два. Выполним проход по числовому ряду и будем зачёркивать все кратные двум числа. Фактически это будет каждое второе число, начиная с четвёрки, поскольку это два в квадрате:

Рисунок 1. Числовой ряд. Автор24 — интернет-биржа студенческих работ

Следующим не зачёркнутым числом будет простое число три. Выполним проход по числовому ряду и зачеркнём все кратные трём числа. А именно каждое третье число, начиная с девятки, поскольку три в квадрате это девять:

Рисунок 2. Числовой ряд. Автор24 — интернет-биржа студенческих работ

Очередным не зачёркнутым числом теперь будет простое число пять. Выполним проход по числовому ряду и зачеркнём все числа, которые кратны пяти. А именно каждое пятое число, начав с двадцати пяти, поскольку это пять в квадрате:

Рисунок 3. Числовой ряд. Автор24 — интернет-биржа студенческих работ

Далее очередным не зачёркнутым числом будет семёрка. Но семь в квадрате это сорок девять, что уже больше тридцати. Значит действие алгоритма закончено и все не простые числа мы уже зачеркнули:

2 3 5 7 11 13 17 19 23 29

Модифицированные варианты решета Эратосфена

Существует версия решета Эратосфена, которая называется неограниченным или постепенным вариантом. Здесь вычисление простых чисел осуществляется последовательно, без верхнего ограничения. Определяются числа, которые находятся в интервалах между составными числами, найденными для всех простых чисел р, начиная с р в квадрате и с шагом р (или 2р, если это нечётные простые числа). Алгоритм может быть представлен в следующем виде:

Рисунок 4. Алгоритм. Автор24 — интернет-биржа студенческих работ

Здесь \ является обозначением разницы среди арифметических прогрессий. Первым простым числом является двойка, что заранее определено, поэтому нет никаких логических ошибок.

Решето Эратосфена иногда могут спутать с алгоритмами поэтапной фильтрации составных чисел, где выполняется тестирование каждого числа, подозреваемого в не простоте, применяя одно простое число на каждом шаге. Одним из таких вариантов является очень популярный функциональный код Дэвида Тёрнера, который часто путают с решетом Эратосфена. Но фактически это не оптимизированный вариант, основанный на переборе делителей. В псевдокоде он записывается так:

Рисунок 5. Псевдокод. Автор24 — интернет-биржа студенческих работ

Источник