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

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

История

Решето Эратосфена в греческом издании Никомаха (греческие числа: γ - 3, ε - 5, ζ - 7, θ - 9, ια - 11, ...)

Первый, опубликованный в новое время, анализ метода решета Эратосфена и его доказательство Хорсли

Этот метод описан во «Введении в арифметику» Никомаха Герасского. Никомах называет автором метода Эратосфена. То же делает и Ямвлих в своём комментарии к этому сочинению Никомаха.

Название «решето» метод получил потому, что во времена Эратосфена писали числа на дощечке, покрытой воском, и прокалывали дырочки в тех местах, где были написаны составные числа. Поэтому дощечка являлась неким подобием решета, через которое «просеивались» все составные числа, а оставались только числа простые.

Никомах, во 2-м веке н. э., объясняет, что метод решета «высеивает» простые числа из нечётных, отделяя от них составные числа, которые он находит, перечисляя для каждого нечетного числа n каждое n-ное число в ряду нечётных чисел, начиная с n. Число 2 он здесь не рассматривал, так как в качестве возможно простых чисел он рассматривал только нечётные.

Символически, используя знак " \ " как «разность множеств», его весьма многословное словесное описание выражает алгоритм

  Primes = {3,5,7,9,...} \ Composites
   
  Composites = { 3n,5n,7n,9n,... for n in {3,5,7,9,...} }

Британец Хорсли, 16 веков спустя, горячо критикует это описание, заявляя что «истинный» метод Эратосфена «наверняка» был «гораздо умнее», начиная с квадратов самих простых чисел прямо в процессе их распознавания:

  Primes = {3,5,7,9,...} \ Composites
   
  Composites = { n²,n²+2n,n²+4n,... for n in Primes }

Алгоритм

Анимация шагов алгоритма Эратосфена для нахождения простых чисел до 120

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

1. Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).
2. Пусть переменная p изначально равна двум — первому простому числу.
3. Зачеркнуть в списке числа от 2p до n, считая шагами по p (это будут числа, кратные p: 2p, 3p, 4p, …).
4. Найти первое незачёркнутое число в списке, большее чем p, и присвоить значению переменной p это число.
5. Повторять шаги 3 и 4, пока возможно.

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

На практике, алгоритм можно улучшить следующим образом. На шаге № 3 числа можно зачеркивать, начиная сразу с числа p², потому что все меньшие числа, кратные p, обязательно имеют простой делитель меньше p, и они уже будут зачеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда p² станет больше, чем n. Кроме того, все простые числа, кроме 2, — нечётные числа, и поэтому для них можно считать шагами по 2p, начиная с p².

Пример для n = 30

Запишем натуральные числа, начиная от 2, до 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

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

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

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

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

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

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

Следующее незачеркнутое число — 7. Его квадрат, 49 — больше 30, поэтому на этом работа завершена. Все составные числа уже зачеркнуты:

2  3     5     7           11    13          17    19          23                29

Псевдокод

Оптимизированная реализация (начинающаяся с квадратов) на псевдокоде:

Вход: натуральное число n
Выход: все простые числа от 2 до n.

Пусть A — булевый массив, индексируемый числами от 2 до n, 
изначально заполненный значениями true.

 для i = 2, 3, 4, ..., пока i2 ≤ n:
  если A[i] = true:
    для j = i2, i2 + i, i2 + 2i, ..., пока j ≤ n:
      назначить A[j] := false

 возвращаем: все числа i, для которых A[i] = true.

Сложность алгоритма

Сложность алгоритма составляет $O(n\log(\log n))$ операций при составлении таблицы простых чисел до $n$.

Доказательство сложности

При выбранном $n\in \mathbb {N}$ для каждого простого $p\in \mathbb {P} \colon p\leq n$ будет выполняться внутренний цикл, который совершит ${\frac {n}{p}}$ действий. Сложность алгоритма можно получить из оценки следующей величины:

$\sum \limits _{p\in \mathbb {P} \colon p\leq n}{\frac {n}{p}}=n\cdot \sum \limits _{p\in \mathbb {P} \colon p\leq n}{\frac {1}{p}}$

Так как количество простых чисел, меньших либо равных $n$, оценивается как ${\frac {n}{\ln n}}$, и, как следствие, $k$-е простое число примерно равно $k\ln k$, то сумму можно преобразовать:

$\sum \limits _{p\in \mathbb {P} \colon p\leq n}{\frac {1}{p}}\approx {\frac {1}{2}}+\sum \limits _{k=2}^{\frac {n}{\ln n}}{\frac {1}{k\ln k}}$

Здесь из суммы выделено слагаемое для первого простого числа, чтобы избежать деления на ноль. Данную сумму можно оценить интегралом

${\frac {1}{2}}+\sum _{k=2}^{\frac {n}{\ln n}}{\frac {1}{k\ln k}}\approx \int \limits _{2}^{\frac {n}{\ln n}}{\frac {1}{k\ln k}}\,dk=\ln \ln k{\Bigr |}_{2}^{\frac {n}{\ln n}}=\ln \ln {\frac {n}{\ln n}}-\ln \ln 2=\ln(\ln n-\ln \ln n)-\ln \ln 2\approx \ln \ln n$

В итоге получается для изначальной суммы:

$\sum \limits _{p\in \mathbb {P} \colon p\leq n}{\frac {n}{p}}\approx n\ln \ln n+o(n)$

Более строгое доказательство (и дающее более точную оценку с точностью до константных множителей) можно найти в книге Hardy и Wright «An Introduction to the Theory of Numbers».

Модификации метода

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

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

 primes = {2,3,...} \ { p², p²+p, ... for p in primes }

используя нотацию абстракции списков, где \ обозначает разницу между арифметическими прогрессиями.

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

Более конкретный псевдокод с поэтапным отсеиванием, в неэффективной реализации, для простоты сравнения с нижеследующими вариантами:

 primes = sieve [2..] where
    sieve [p, ...xs] = [p, ...sieve (xs \ [p², p²+p..])]

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

 primes = [2, ...sieve primes [3..]] where
    sieve [p, ...ps] [...h, p², ...xs]
         = [...h, ...sieve ps (xs \ [p², p²+p..])]

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

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

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

 primes = sieve [2..] where
    sieve [p, ...xs] = [p, ...sieve [x in xs if x%p > 0]]

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

Сегментированное решето

Как замечает Соренсон, главной проблемой реализации решета Эратосфена на вычислительных машинах является не количество выполняемых операций, а требования по объёму занимаемой памяти (впрочем, его замечание относится к неактуальному сейчас компьютеру DEC VAXstation 3200, выпущенному в 1989 году). При больших значениях n, диапазон простых чисел может превысить доступную память; хуже того, даже при сравнительно небольших n использование кэша памяти далеко от оптимального, так как алгоритм, проходя по всему массиву, нарушает принцип локализованности ссылок.

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

1. Разделяем диапазон от 2 до n на отрезки (сегменты) некоторой длины Δ ≤ √n.
2. Находим все простые числа в первом отрезке, используя обычное решето.
3. Каждый из последующих отрезков оканчивается на некотором числе m. Находим все простые числа в отрезке следующим образом:
   1. Создаем булевый массив размера Δ
   2. Для каждого простого числа p ≤ √m из уже найденных, отмечаем в массиве как «непростые» все числа кратные p, перебирая числа с шагом в p, начиная с наименьшего кратного p числа в данном отрезке.

Если число Δ выбрано равным √n, то сложность алгоритма по памяти оценивается как O(√n), а операционная сложность остаётся такой же, что и у обычного решета Эратосфена.

Для случаев, когда n настолько велико, что все просеиваемые простые числа меньшие √n не могут уместиться в памяти, как того требует алгоритм сегментированного сита, используют более медленные, но с гораздо меньшими требованиями по памяти алгоритмы, например решето Соренсона.

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

Доказательство тождества Эйлера для дзета-функции Римана содержит механизм отсеивания составных чисел подобный решету Эратосфена, но так, что каждое составное число удаляется из списка только один раз. Схожее решето описано в Gries & Misra 1978 г. как решето с линейным временем работы (см. ниже).

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

[2] (3) 5  7  9 11  13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79  ...
[3]    (5) 7    11  13    17 19    23 25    29 31    35 37    41 43    47 49    53 55    59 61    65 67    71 73    77 79  ...
[4]       (7)   11  13    17 19    23       29 31       37    41 43    47 49    53       59 61       67    71 73    77 79  ...
[5]            (11) 13    17 19    23       29 31       37    41 43    47       53       59 61       67    71 73       79  ...
[...] 

Здесь показан пример начиная с нечетных чисел, после первого этапа алгоритма. Таким образом, после k-го этапа рабочий список содержит только числа взаимно простые с первыми k простыми числами (то есть числа не кратные ни одному из первых k простых чисел), и начинается с (k+1)-го простого числа. Все числа в списке, меньшие квадрата его первого числа, являются простыми.

В псевдокоде,

 primes = sieve [2..] where
    sieve [p, ...xs] = [p, ...sieve (xs \ [p², ...p*xs])]

Решето только по нечётным числам

Поскольку все чётные числа, кроме 2, — составные, то можно вообще не обрабатывать никак чётные числа, а оперировать только нечётными числами. Во-первых, это позволит вдвое сократить объём требуемой памяти. Во-вторых, это уменьшит количество выполняемых алгоритмом операций (примерно вдвое).

В псевдокоде:

 primes = [2, ...sieve [3,5..]] where
    sieve [p, ...xs] = [p, ...sieve (xs \ [p², p²+2p..])]

Это можно обобщить на числа взаимно простые не только с 2 (то есть нечетные числа), но также и с 3, 5, и т. д..

Уменьшение объёма потребляемой памяти

Алгоритм Эратосфена фактически оперирует с $n$ битами памяти. Следовательно, можно существенно сэкономить потребление памяти, храня $n$ переменных булевского типа не как $n$ байт, а как $n$ бит, то есть $n/8$ байт памяти.

Такой подход — «битовое сжатие» — усложняет оперирование этими битами. Любое чтение или запись бита будут представлять собой несколько арифметических операций. Но с другой стороны существенно улучшается компактность в памяти. Бо́льшие интервалы умещаются в кэш-память которая работает гораздо быстрее обычной так что при работе по-сегментно общая скорость увеличивается.

Решето Эратосфена с линейным временем работы

Этот алгоритм находит составные числа как перечисление формулы

{ (piqjrk...) for p,q,r,... in primes, where i+j+k+... > 1 }

Для этого поддерживается список простых чисел pr[], поначалу пустой. В ходе работы алгоритма этот список будет постепенно дополняться и в конце работы будет содержать все простые числа от 2 до n.

Также поддерживается массив lp[] (lp от англ. least prime) где для всех i от 2 до n, lp[i] будет содержать минимальный простой делитель числа i. Изначально все величины lp[i] равны 0.

Дальше перебираем числа i от 2 до n в порядке возрастания. Для каждого i:

1. Если lp[i] ≠ 0, это означает, что текущее число i — составное, и его минимальным простым делителем является lp[i].

2. Если lp[i] = 0, это означает, что текущее число i — простое, так как для него так и не обнаружилось других делителей. Присваиваем lp[i] = i и добавляем i в конец списка pr[].

3. Итак, lp[i] является минимальным простым делителем числа i. Для всех p последовательно взятых из pr[], не превосходящих lp[i], назначаем lp[p ⋅ i] = p.

Утверждается, что таким образом каждое значение в lp[] назначается только один раз.

Псевдокод

 Вход: натуральное число n

 Пусть pr - целочисленный список, поначалу пустой;
       lp - целочисленный массив, индексируемый от 2 до n, заполненный нулями

 для i := 2, 3, 4, ..., до n: 
   если lp[i] = 0:
       lp[i] := i
       pr[] += {i}
   для p из pr пока p ≤ lp[i] и p*i ≤ n:
       lp[p*i] := p

Выход: все числа в списке pr.

Сложность алгоритма на практике

Решето Эратосфена является популярным способом оценки производительности компьютера. Как видно из вышеизложенного доказательства сложности алгоритма, избавившись от константы и слагаемого очень близкого к нулю (ln (ln n - ln ln n) - ln ln 2 ≈ ln ln n), временная сложность вычисления всех простых чисел меньше n аппроксимируется следующим соотношением O(n ln ln n). Однако алгоритм имеет экспоненциальную временную сложность в отношении размера входных данных, что делает его псевдополиномиальным алгоритмом. Памяти же для базового алгоритма требуется O(n).

Сегментированная версия имеет ту же операционную сложность O(n ln ln n),. что и несегментированная версия, но уменьшает потребность в используемой памяти до размера сегмента (размер сегмента значительно меньше размера всего массива простых чисел), который равен O(√n/ln n). Также существует очень редко встречающееся на практике оптимизированное сегментированное решето Эратосфена. Оно строится за O(n) операций и занимает O(√n ln ln n/ln n) бит в памяти.

На практике оказывается, что оценка ln ln n не очень точна даже для максимальных практических диапазонов таких как 10¹⁶. Ознакомившись с вышеописанным доказательством сложности, нетрудно понять откуда взялась неточность оценки. Расхождение с оценкой можно объяснить следующим образом: в пределах данного практического диапазона просеивания существенное влияние оказывают постоянные смещения. Таким образом очень медленно растущий член ln ln n не становится достаточно большим, чтобы константами можно было справедливо пренебречь, до тех пор пока n не приблизится к бесконечности, что естественно выходит за границы любого прикладного диапазона просеивания. Данный факт показывает, что для актуальных на сегодняшний день входных данных производительность решета Эратосфена намного лучше, чем следовало ожидать, используя только асимптотические оценки временной сложности.

Решето Эратосфена работает быстрее, чем часто сравниваемое с ним решето Аткина только для значений n меньших 10 ¹⁰ . Сказанное справедливо при условии, что операции занимают примерно одно и то же время в циклах центрального процессора, а это является разумным предположением для одного алгоритма, работающего с огромным битовым массивом. С учётом этого предположения получается, что сито Аткина быстрее чем максимально факторизованное решето Эратосфена для n свыше 10 ¹³ , но при таких диапазонах просеивания потребуется занять огромное пространство в оперативной памяти, даже если была использована «битовая упаковка». Однако раздел о сегментированной версии решета Эратосфена показывает, что предположение о сохранении равенства во времени, затрачиваемом на одну операцию, между двумя алгоритмами не выполняется при сегментации. В свою очередь это приводит к тому, что решето Аткина (несегментированное) работает медленнее, чем сегментированное решето Эратосфена с увеличением диапазона просеивания, за счёт уменьшения времени на операцию для второго.

Использование нотации O большого также не является правильным способом сравнения практических характеристик даже для вариаций решета Эратосфена, поскольку данная нотация игнорирует константы и смещения, которые могут быть очень значительными для прикладных диапазонов. Например, одна из вариаций решета Эратосфена известная как решето Притчарда имеет производительность O(n), но её базовая реализация требует либо алгоритма «одного большого массива» (то есть использования обычного массива, в котором хранятся все числа до n), который ограничивает его диапазон использования до объёма доступной памяти, либо он должен быть сегментирован для уменьшения использования памяти. Работа Притчарда уменьшила требования к памяти до предела, но платой за данное улучшение по памяти является усложнение вычислений, что приводит увеличению операционной сложности алгоритмов.

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

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

• Умножение и деление. При аналитических расчётах предполагается, что скорость выполнения арифметических операций равноценна. Но на самом деле это не так, и умножение, и деление выполняются гораздо медленнее, чем сложение и вычитание. Таким образом данный фактор никак не влияет на решето Эратосфена, поскольку оно использует только сложение и вычитание, но является весьма существенным для решета Питчарда (один из результатов усложнения вычислений упомянутого выше).
• Оптимизация компилятора. Компилятор оптимизирует на стадии компиляции все программы для более корректного исполнения машиной. Но часто бывает очень сложно сказать, какой вклад даёт данная оптимизация, и будет ли этот вклад одинаковым для двух различных алгоритмов.
• Кэш. Процессор использует кэш, чтобы ускорить извлечение инструкций и данных из памяти. Наличие кэша приводит к тому, что программы, использующие локализованные ссылки, будут работать быстрее. Но алгоритмы просеивания простых чисел, которые используют факторизацию высокой степени, часто генерируют случайные ссылки в память, что снижает их производительность.

Для наглядности представления вклада факторизации в производительность алгоритмов просеивания ниже приведены две таблицы. В таблицах приведены результаты измерения реального времени исполнения решета Эратосфена и решета Питчарда в секундах для разных диапазонов n и разных степеней кольцевой факторизации. E_i и P_i обозначения для решета Эратосфена и Питчарда соответственно, где индекс i означает степень кольцевой факторизации. E₀ и P₀ означают отсутствие факторизации.

n	E0	E1	E2	E3	E4	E5
500	0.00043	0.00029	0.00027	0.00048	0.00140	0.01035
5000	0.00473	0.00305	0.00254	0.00293	0.00551	0.03207
50000	0.05156	0.03281	0.02617	0.02578	0.03164	0.10663
500000	0.55817	0.35037	0.28240	0.28358	0.28397	0.47028
5000000	6.06719	3.82905	3.20722	3.25214	3.28104	3.38455

Из таблицы видно, что лучшую производительность имеет решето Эратосфена со средней степенью факторизации E₂. Данный факт можно объяснить влиянием кэш-фактора, рассмотренного выше, на алгоритмы с высокой степенью факторизации.

n	P0	P1	P2	P3	P4	P5
500	0.00147	0.00074	0.00050	0.00051	0.00095	0.00649
5000	0.01519	0.00777	0.00527	0.00453	0.00430	0.00973
50000	0.15507	0.08203	0.05664	0.04843	0.04180	0.04413
500000	1.60732	0.86254	0.61597	0.53825	0.47146	0.43787
5000000	16.47706	9.00177	6.57146	5.83518	5.27427	4.88251

С увеличением n соотношение времен становится всё больше в пользу решета Эратосфена, а на диапазоне n = 5000000 оно стабильно быстрее при любых факторизациях. Данный факт ещё раз подтверждает проигрыш в быстродействии решета Питчарда из-за сложных вычислений.

См. также

• Решето Сундарама
• Решето Аткина
• Решето Притчарда
• Корекурсия

Литература

• Эратосфеново решето // Элоквенция — Яя. — М. : Советская энциклопедия, 1957. — С. 141. — (Большая советская энциклопедия : [в 51 т.] / гл. ред. Б. А. Введенский ; 1949—1958, т. 49).
• Гальперин Г. «Просто о простых числах» // Квант. — 1987. — № 4. — С. 10—14,38.
• Неопубликованные материалы Л.Эйлера по теории чисел / РАН, Институт истории естествознания и техники, С.-Петерб. фил.; Сост. Матвиевская Г.П. [и др.]; Отв. ред. Невская Н.И. — СПб.: Наука, 1997. — ISBN 5-02-024847-9.
• Проф. Д.Ф.Егоров. Элементы теории чисел. — Государственное издательство Москва, 1923. (недоступная ссылка)
• Кордемский Б. А. Математическая смекалка. — М.: ГИФМЛ, 1958. — 576 с.

Ссылки

• Решето Эратосфена от М. Гарднера
• Алгоритм составления таблицы простых чисел от заданного до другого числа
• Реализация алгоритма поиска простых чисел на Java
• Доказательство сложности алгоритма
• Еще раз о поиске простых чисел