WikiSort.ru - Не сортированное

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

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

${\displaystyle \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}}}$

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

${\displaystyle \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}}}$

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

${\displaystyle {\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}$

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

${\displaystyle \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»^[6].

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

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

 primes = [2..] \ [[p², p²+p..] for p in primes]

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

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

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

 primes = sieve [2..] where

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

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

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

Широко известный функциональный код Дэвида Тёрнера 1975 г.^[9] часто принимают за решето Эратосфена,^[8] но на самом деле^[7] это неоптимальный вариант с перебором делителей (в оптимальном варианте не используются делители, большие квадратного корня тестируемого числа). В псевдокоде,

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

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

Как отмечает Соренсон, главной проблемой реализации решета Эратосфена на вычислительных машинах является не количество выполняемых операций, а требования по объёму занимаемой памяти.^[4] При больших значениях n, диапазон простых чисел может превысить доступную память; хуже того, даже при сравнительно небольших n использование кэша памяти далеко от оптимального, так как алгоритм, проходя по всему массиву, нарушает принцип локализованности ссылок^[en].

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

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

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

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

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

Доказательство тождества Эйлера для дзета-функции Римана содержит механизм отсеивания составных чисел подобный решету Эратосфена, но так, что каждое составное число удаляется из списка только один раз. Схожее решето описано в 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*x for x in xs]])]

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

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

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

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

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

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

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

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

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

Изначально все величины lp[i] заполним нулями.

Дальше следует перебрать текущее число i от 2 до n. Здесь может быть два случая:

• lp[i] = 0: это означает, что число i — простое, так как для него так и не обнаружилось других делителей.

Следовательно, надо присвоить lp[i] = i и добавить i в конец списка pr[].

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

В обоих случаях дальше начинается процесс расстановки значений в массиве lp[i]: следует брать числа, кратные i, и обновлять у них значение lp[]. Однако основная цель — научиться делать это таким образом, чтобы в итоге у каждого числа значение lp[] было бы установлено не более одного раза.

Утверждается, что для этого можно поступить таким образом. Рассматриваются числа вида x = p ⋅ i, где p последовательно равно всем простым числам не превосходящим lp[i] (как раз для этого понадобилось хранить список всех простых чисел).

У всех чисел такого вида проставим новое значение lp[x] — оно должно быть равно p^[13].

 Вход: натуральное число 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.