Решето Эратосфена
Решето́ Эратосфе́на — алгоритм нахождения всех простых чисел до некоторого целого числа Шаблон:Math, который приписывают древнегреческому математику Эратосфену Киренскому<ref name="nicomachus">Никомах Герасский, Введение в арифметику, I, XIII, 2. по-гречески, по-русски Шаблон:Wayback</ref>. Название алгоритма говорит о принципе его работы: алгоритм осуществляет Шаблон:Iw списка чисел от 2 до Шаблон:Math. По мере прохождения списка составные числа исключаются, а простые остаются.
История
Этот метод описан во «Введении в арифметику» Никомаха Герасского. Никомах называет автором метода Эратосфена. То же делает и Ямвлих в своём комментарии к этому сочинению Никомаха.
Название «решето» метод получил потому, что во времена Эратосфена писали числа на дощечке, покрытой воском, и прокалывали дырочки в тех местах, где были написаны составные числа. Поэтому дощечка являлась неким подобием решета, через которое «просеивались» все составные числа, а оставались только числа простые<ref>Шаблон:Книга</ref>.
Никомах, во II веке н. э., объясняет, что метод решета «высеивает» простые числа из нечётных, отделяя от них составные числа, которые он находит, перечисляя для каждого нечетного числа n все его кратные числа как каждое n-ное число в ряду нечётных чисел, начиная с n. Число 2 он здесь не рассматривал, так как в качестве возможно простых чисел он рассматривал только нечётные<ref name="nicomachus" />.
Символически, используя знак " Шаблон:Math " как «разность множеств», его весьма многословное словесное описание выражает алгоритм
Primes = {3,5,7,9,...} \ Composites
Composites = { 3n,5n,7n,9n,... for n in {3,5,7,9,...} }
где каждая последовательность "3n,5n,7n,9n ..." находится прямым перечислением как указано выше, без умножений.
Британец Шаблон:Iw, 16 веков спустя, горячо критикует это описание, заявляя что «истинный» метод Эратосфена «наверняка» был «гораздо умнее», начиная перечисление кратных с квадратов самих простых чисел прямо в процессе их распознавания<ref name="horsley" />:
Primes = {3,5,7,9,...} \ Composites
Composites = { n²,n²+2n,n²+4n,... for n in Primes }
Алгоритм
Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:
- Выписать подряд все целые числа от двух до n (2, 3, 4, ..., n).
- Пусть переменная p изначально равна двум — первому простому числу.
- Зачеркнуть в списке числа от 2p до n, считая шагами по p (это будут числа, кратные p: 2p, 3p, 4p, ...).
- Найти первое незачёркнутое число в списке, большее чем p, и присвоить значению переменной p это число.
- Повторять шаги 3 и 4, пока возможно.
Теперь все незачёркнутые числа в списке — это все простые числа от 2 до n.
На практике, алгоритм можно улучшить следующим образом. На шаге № 3 числа можно зачеркивать, начиная сразу с числа p2, потому что все меньшие числа, кратные p, обязательно имеют простой делитель меньше p, и они уже будут зачеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда p2 станет больше, чем n.<ref name="horsley" /> Кроме того, все простые числа, кроме 2, — нечётные числа, и поэтому для них можно считать шагами по 2p, начиная с p2.
Пример для n = 30
Запишем натуральные числа, начиная от Шаблон:Math, до Шаблон:Math в ряд:
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
Первое число в списке, Шаблон:Math — простое. Пройдём по ряду чисел, зачёркивая все числа, кратные Шаблон:Math (то есть, каждое второе, начиная с Шаблон:Math):
2 3456789101112131415161718192021222324252627282930
Следующее незачеркнутое число, Шаблон:Math — простое. Пройдём по ряду чисел, зачёркивая все числа, кратные Шаблон:Math (то есть, каждое третье, начиная с Шаблон:Math):
2 3456789101112131415161718192021222324252627282930
Следующее незачеркнутое число, Шаблон:Math — простое. Пройдём по ряду чисел, зачёркивая все числа, кратные 5 (то есть, каждое пятое, начиная с Шаблон:Math):
2 3456789101112131415161718192021222324252627282930
Следующее незачеркнутое число — Шаблон:Math. Его квадрат, Шаблон:Math — больше Шаблон:Math, поэтому на этом работа завершена. Все составные числа уже зачеркнуты:
2 3 5 7 11 13 17 19 23 29
Псевдокод
Оптимизированная реализация (начинающаяся с квадратов) на псевдокоде<ref name="sedgewick">Шаблон:Книга, p. 16.</ref><ref name="intro">Jonathan Sorenson, An Introduction to Prime Number Sieves Шаблон:Wayback, Computer Sciences Technical Report #909, Department of Computer Sciences University of Wisconsin-Madison, January 2 1990 (the use of optimization of starting from squares, and thus using only the numbers whose square is below the upper limit, is shown).</ref>:
Вход: натуральное число 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.
Сложность алгоритма
Сложность алгоритма составляет <math>O(n \log (\log n))</math> операций при составлении таблицы простых чисел до <math>n</math><ref>Pritchard, Paul, "Linear prime-number sieves: a family tree, " Sci. Comput. Programming 9:1 (1987), pp. 17-35.</ref>.
Доказательство сложности
При выбранном <math>n \in \mathbb{N}</math> для каждого простого <math>p \in \mathbb{P}\colon p \le n</math> будет выполняться внутренний цикл<ref>Строго говоря, внутренний цикл выполняется для каждого простого <math>p \in \mathbb{P}\colon p \le (\sqrt n)</math>, но <math>O(\log (\log n))</math> = <math>O(\log (\log (\sqrt n)))</math>, поэтому, традиционно, для краткости, квадратный корень опускают.</ref>, который совершит <math>\frac{n}{p}</math> действий. Сложность алгоритма можно получить из оценки следующей величины:
<math> \sum\limits_{p\in \mathbb{P}\colon p \le n} {\frac{n}{p}} = n\cdot\sum\limits_{p\in \mathbb{P}\colon p \le n} {\frac{1}{p}} </math>
Так как количество простых чисел, меньших либо равных <math>n</math>, оценивается как <math>\frac{n}{\ln n}</math>, и, как следствие, <math>k</math>-е простое число примерно равно <math>k\ln k</math>, то сумму можно преобразовать:
<math> \sum\limits_{p \in \mathbb{P}\colon p \le n}\frac{1}{p}\approx \frac{1}{2} + \sum\limits_{k=2}^{\frac{n}{\ln n}}\frac{1}{k\ln k}</math>
Здесь из суммы выделено слагаемое для первого простого числа, чтобы избежать деления на ноль. Данную сумму можно оценить интегралом
<math> \frac{1}{2} + \sum^{\frac{n}{\ln n}}_{k=2}{\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 </math>
В итоге получается для изначальной суммы:
<math> \sum\limits_{p\in \mathbb{P}\colon p \le n} {\frac{n}{p}} \approx n \ln \ln n + o(n)</math>
Более строгое доказательство (и дающее более точную оценку с точностью до константных множителей) можно найти в книге Hardy и Wright «An Introduction to the Theory of Numbers»<ref name="автоссылка2">Hardy and Wright "An Introduction to the Theory of Numbers, p. 349</ref>.
Модификации метода
Неограниченный, постепенный вариант
В этом варианте простые числа вычисляются последовательно, без ограничения сверху,<ref name="ONeill">O’Neill, Melissa E., «The Genuine Sieve of Eratosthenes» Шаблон:Wayback, Journal of Functional Programming, Published online by Cambridge University Press 9 October 2008 Шаблон:Doi.</ref> как числа, находящиеся в промежутках между составными числами, которые вычисляются для каждого простого числа Шаблон:Math, начиная с его квадрата, с шагом в Шаблон:Math (или для нечетных простых чисел Шаблон:Math)<ref name="horsley">Horsley, Rev. Samuel, F. R. S., "{{#if:el|{{#if:|{{{зачин}}} }}{{#if:||{{#switch:el |ab=абхазск. |abq=абазинск. |af=африкаанс |akk=аккадск. |akz=алабама |ale=алеутск. |als=тоскск. |am=амхарск. |an=арагонск. |ang=др.-англ. |ani=андийск. |ar=арабск. |arc=арамейск. |av=аварск. |ae|ave=авест. |awd=аравакск. |az=азерб. |eu=баскск. |ba=башк. |bar=бав. |be=белор. |ber=берберск. |bg=болг. |bn=бенг. |bo=тибетск. |br=брет. |bs=босн. |bua=бурятск. |ca=каталанск. |ce=чеченск. |cel=галльск. |cel-pro=пракельт. |ch=чам. |chm=мар. |cho=чокт. |chu-ru=русск.-церк.-слав. |chu-sr=сербск.-церк.-слав. |chu-bg=болг.-церк.-слав. |cjs=шорск. |ckt=чук. |co=корс. |crh=кр.-тат. |cs=чешск. |csb=кашубск. |cu=ст.-слав. |cv=чувашск. |cy=валл. |da=датск. |dar=дарг. |ddo=цезск. |de=нем. |dsb=н.-луж. |dty=дотели |dum=ср.-нидерл. |egy=егип. |el=греч. |en=англ. |enm=ср.-англ. |eo=эспер. |es=исп. |et=эст. |ett=этрусск. |fa=перс. |fi=финск. |fo=фарерск. |fr=франц. |frk=др.-франкск. |frm=ср.-франц. |fro=ст.-франц. |frr=сев.-фризск. |fry=зап.-фризск. |fur=фриульск. |fy=фризск. |ga=ирл. |gag=гагаузск. |gd=гэльск. |gdo=годобер. |gem=прагерм. |gez=древнеэфиопск. |gin=гинухск. |gkm=ср.-греч. |gl=галис. |gmh=ср.-в.-нем. |gml=ср.-н.-нем. |gmy=микен. |gn=гуарани |goh=др.-в.-нем. |got=готск. |grc=др.-греч. |grc-pro|grk-pro=протогреч. |gsw=алеманнск. |gu=гуджарати |ha=хауса |haw=гавайск. |hbo=др.-евр. |hbs=сербохорв. |he=ивр. |hi=хинд. |hit=хетт. |hr=хорв. |hsb=в.-луж. |ht=гаит. |hu=венг. |hy=армянск. |id=индон. |inh=ингушск. |is=исл. |it=итал. |itl=ительм. |iu=инукт. |ja=яп. |jv=яванск. |ka=груз. |kaa=каракалп. |kas=кашм. |kg=конго |kik=кикуйю |kjh=хакас. |kk=казахск. |kky=кууку-йимитирск. |kl=гренландск. |kn=канн. |ko=корейск. |kom=коми-зыр. |koi=коми-перм. |krc=карач.-балк. |krl=карельск. |kum=кумыкск. |ky=кирг. |la=лат. |lad=сефардск. |lb=люксемб. |lez=лезг. |liv=лив. |lmo=ломбардск. |lng=лангобардск. |lo=лаосск. |lt=лит. |ltg=латг. |lv=латышск. |mad=мадурск. |mdf=мокш. |mg=малаг. |mga=ср.-ирл. |mi=маори |mic=микмакск. |mk=макед. |mn=монг. |mnc=маньчжурск. |mns=мансийск. |mnw=монск. |ms=малайск. |mt=мальтийск. |myv=эрзянск. |myz=мандейск. |na=науру |nah=науатль |niv=нивх. |nds=нж.-нем. |ne=непали |nl=нидерл. |no=норв. |non=др.-сканд. |nuk=нутка |oc=прованс. |ojp=ст.-яп. |orv=др.-русск. |os=осет. |osp=ст.-исп. |osx=др.-сакс. |ota=османск. |otk=др.-тюрк. |pa=пендж. |pap=папьям. |pcd=пикардск. |pdc=пенсильв.-нем. |peo=др.-перс. |phn=финик. |pi=пали |pie=праиндоевр. |pl=польск. |pox=полабск. |ppol=праполинез. |pro=ст.-оксит. |prg=др.-прусск. |pt=порт. |pt-BR=браз.-порт. |qu=кечуа |rm=ретором. |ro=рум. |roa-nor=нормандск. |rom=цыганск. |ru=русск. |rw=киньяруанда |sa=санскр. |sah=якутск. |sc=сард. |scn=сицил. |sco=скотс. |se=северносаамск. |see=сенека |sga=др.-ирл. |sh=сербохорв. |shh=шошонск. |sjd=кильдин-саамск. |sjt=терско-саамск. |sk=словацк. |sl=словенск. |sla-pro=праслав. |smi-pro=прасаамск. |smn=инари-саамск. |sms=коллта-саамск. |sqi|sq=алб. |sr=сербск. |sux=шумерск. |sv=шведск. |sw=суах. |syc=сирийск. |syd=самодийск. |ta=там. |tab=табасаранск. |tg=тадж. |th=тайск. |tin=тинд. |tk=туркм. |tl=тагальск. |tn=тсвана |tnq=таино |tpn=тупи |tr=тур. |trk=тюрк. |tt=тат. |ttt=татск. |txb=тохар. B |ty=таитянск. |tyv=тувинск. |udm=удм. |ug=уйгурск. |uga=угаритск. |uk=укр. |ur=урду |urj-pro=прауральск. |uz=узб. |vec=венет. |vi=вьетн. |vot=водск. |vsn=др.-инд. |xas=камас. |xal=калм. |xcl=грабар |xh=коса |xil=иллир. |xld=лидийск. |xmf=мегр. |xno=англ.-норм. |xpr=парфянск. |xpu=пуническ. |xto=тохар. A |yi=идиш |yrk=ненецк. |zh=кит. |zu=зулусск. |el.}}}}}}{{#if:Κόσκινον Ερατοσθένους|{{#if:el|{{#if:|| }}}}Шаблон:Aslinks{{#if:|Ошибка скрипта: Модуля «string» не существует.}}}}{{#if:| }}{{#if:| «{{{3}}}{{#if:|, {{{4}}}}}{{#if:|, {{{5}}}}}»}}{{#if:| ({{{comment}}})}}{{#if:|}}{{#if:|Шаблон:Категория}}{{#if:|Шаблон:Категория}}{{#if:|Шаблон:Категория}} or, The Sieve of Eratosthenes. Being an Account of His Method of Finding All the Prime Numbers, " Philosophical Transactions (1683—1775), Vol. 62. (1772), pp. 327—347 Шаблон:Wayback.</ref>. Может быть представлен абстрактно в парадигме потоков данных как
primes = {2,3,...} \ { p², p²+p, ... for p in primes }
используя нотацию абстракции списков, где \ обозначает разницу между арифметическими прогрессиями.
Первое простое число Шаблон:Math (среди возрастающих положительных целых чисел) заранее известно, поэтому в этом самореферентном определении нет порочного круга.
Более конкретный псевдокод с поэтапным отсеиванием, в неэффективной реализации, для простоты сравнения с нижеследующими вариантами:
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..])]
Перебор делителей
Решето Эратосфена часто путают с алгоритмами, которые поэтапно Шаблон:Iw составные числа, тестируя каждое из чисел-кандидатов на делимость по одному простому числу на каждом этапе.<ref name="Runciman">Colin Runciman, «FUNCTIONAL PEARL: Lazy wheel sieves and spirals of primes», Journal of Functional Programming, Volume 7 Issue 2, March 1997; также здесь Шаблон:Wayback.</ref>
Широко известный функциональный код Дэвида Тёрнера 1975 г.<ref>Turner, David A. SASL language manual. Tech. rept. CS/75/1. Department of Computational Science, University of St. Andrews 1975. (primes = sieve [2..]; sieve (p:nos) = p:sieve (remove (multsof p) nos); remove m = filter (not . m); multsof p n = rem n p==0)</ref> часто принимают за решето Эратосфена,<ref name="Runciman"/> но на самом деле<ref name="ONeill" /> это неоптимальный вариант с перебором делителей:
primes = sieve [2..] where
sieve [p, ...xs] = [p, ...sieve [x in xs if x%p > 0]]
В оптимальном варианте не используются делители, большие квадратного корня тестируемого числа.
Сегментированное решето
Как замечает Соренсон, главной проблемой реализации решета Эратосфена на вычислительных машинах является не количество выполняемых операций, а требования по объёму занимаемой памяти (впрочем, его замечание относится к неактуальному сейчас компьютеру DEC VAXstation 3200, выпущенному в 1989 году).Шаблон:R При больших значениях Шаблон:Mvar, диапазон простых чисел может превысить доступную память; хуже того, даже при сравнительно небольших Шаблон:Mvar использование кэша памяти далеко от оптимального, так как алгоритм, проходя по всему массиву, нарушает принцип Шаблон:Iw.
Для решения представленной проблемы используется сегментированное решето, в котором за итерацию просеивается только часть диапазона простых чисел.<ref>Crandall & Pomerance, Prime Numbers: A Computational Perspective, second edition, Springer: 2005, pp. 121-24.</ref> Данный метод известен с 1970-х годов и работает следующим образом:Шаблон:R<ref name="автоссылка4">Шаблон:Статья</ref>
- Разделяем диапазон от 2 до Шаблон:Mvar на отрезки (сегменты) некоторой длины Шаблон:Math.
- Находим все простые числа в первом отрезке, используя обычное решето.
- Каждый из последующих отрезков оканчивается на некотором числе Шаблон:Mvar. Находим все простые числа в отрезке следующим образом:
- Создаем булевый массив размера Шаблон:Math
- Для каждого простого числа Шаблон:Math из уже найденных, отмечаем в массиве как «непростые» все числа кратные Шаблон:Math, перебирая числа с шагом в Шаблон:Math, начиная с наименьшего кратного Шаблон:Math числа в данном отрезке.
Если число Шаблон:Math выбрано равным Шаблон:Math, то сложность алгоритма по памяти оценивается как Шаблон:Math, а операционная сложность остаётся такой же, что и у обычного решета Эратосфена.<ref name="автоссылка4" />
Для случаев, когда Шаблон:Mvar настолько велико, что все просеиваемые простые числа меньшие Шаблон:Math не могут уместиться в памяти, как того требует алгоритм сегментированного сита, используют более медленные, но с гораздо меньшими требованиями по памяти алгоритмы, например решето Соренсона.<ref>J. Sorenson, The pseudosquares prime sieve Шаблон:Wayback, Proceedings of the 7th International Symposium on Algorithmic Number Theory. (ANTS-VII, 2006).</ref>
Решето Эйлера
Доказательство тождества Эйлера для дзета-функции Римана содержит механизм отсеивания составных чисел подобный решету Эратосфена, но так, что каждое составное число удаляется из списка только один раз. Схожее решето описано в Gries & Misra 1978 г. как решето с линейным временем работы (см. ниже).
Составляется исходный список начиная с числа Шаблон:Math. На каждом этапе алгоритма первый номер в списке берется как следующее простое число, результаты произведения которого на каждое число в списке помечаются для последующего удаления. После этого из списка убирают первое число и все помеченные числа, и процесс повторяется вновь:
[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 ... [...]
Здесь показан пример начиная с нечетных чисел, после первого этапа алгоритма. Таким образом, после Шаблон:Math-го этапа рабочий список содержит только числа взаимно простые с первыми Шаблон:Math простыми числами (то есть числа не кратные ни одному из первых Шаблон:Math простых чисел), и начинается с Шаблон:Math-го простого числа. Все числа в списке, меньшие квадрата его первого числа, являются простыми.
В псевдокоде,
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, и т. д..
Уменьшение объёма потребляемой памяти
Алгоритм Эратосфена фактически оперирует с <math>n</math> битами памяти. Следовательно, можно существенно сэкономить потребление памяти, храня <math>n</math> переменных булевского типа не как <math>n</math> байт, а как <math>n</math> бит, то есть <math>n/8</math> байт памяти.
Такой подход — «битовое сжатие» — усложняет оперирование этими битами. Любое чтение или запись бита будут представлять собой несколько арифметических операций. Но с другой стороны существенно улучшается компактность в памяти. Бо́льшие интервалы умещаются в кэш-память которая работает гораздо быстрее обычной так что при работе по-сегментно общая скорость увеличивается.
Решето Эратосфена с линейным временем работы
Этот алгоритм находит составные числа как перечисление формулы
{ (piqjrk...) for p,q,r,... in primes, where i+j+k+... > 1 }
Для этого поддерживается список простых чисел Шаблон:Math, поначалу пустой. В ходе работы алгоритма этот список будет постепенно дополняться и в конце работы будет содержать все простые числа от Шаблон:Math до Шаблон:Math.
Также поддерживается массив Шаблон:Math (Шаблон:Math от англ. Шаблон:Lang-en2) где для всех Шаблон:Math от Шаблон:Math до Шаблон:Math, Шаблон:Math будет содержать минимальный простой делитель числа Шаблон:Math. Изначально все величины Шаблон:Math равны Шаблон:Math.
Дальше перебираем числа Шаблон:Math от Шаблон:Math до Шаблон:Math в порядке возрастания. Для каждого Шаблон:Math:
- Если Шаблон:Math, это означает, что текущее число Шаблон:Math — простое, так как для него так и не обнаружилось других делителей. Присваиваем Шаблон:Math и добавляем Шаблон:Math в конец списка Шаблон:Math.
- Если Шаблон:Math, это означает, что текущее число Шаблон:Math — составное, и его минимальным простым делителем является Шаблон:Math.
- Итак, Шаблон:Math является минимальным простым делителем числа Шаблон:Math. Для всех Шаблон:Math последовательно взятых из Шаблон:Math, не превосходящих Шаблон:Math, назначаем Шаблон:Math.
Утверждается, что таким образом каждое значение в Шаблон:Math назначается только один раз<ref>David Gries, Jayadev Misra. A Linear Sieve Algorithm for Finding Prime Numbers [1978]</ref>.
Псевдокод линейного варианта
Вход: натуральное число n
Пусть pr - целочисленный список, поначалу пустой;
lp - целочисленный массив, индексируемый от 2 до n, заполненный нулями
для i := 2, 3, 4, ..., до n:
если lp[i] ≡ 0:
lp[i] := i
pr[] += {i}
для p из pr пока i*p ≤ n:
lp[i*p] := p
если p ≡ lp[i]:
прервать перечисление p
Выход: все числа в списке pr.
Если вместо непрерывного массива использовать саморасширяющийся ассоциативный массив и убрать из этого псевдокода все упоминания числа n то он превращается в псевдокод, описывающий неограниченный постепенный алгоритм для нахождения простых чисел, одного за другим, без ограничения сверху. В функциональном псевдокоде,
primes = go 2 [] WHERE
go i [(j,q), ...r]
| i==j = go (i+1) (r ⋃ mark (j,q)) , ORELSE
go i lp = [i, ...go (i+1) (lp ⋃ mark (i,i))]
mark (i,q) = [(i*p,p) FOR p IN primes UNTIL q]
Но из линейного он превращается в квадратичный, или ещё хуже, так как перепроизводство составных чисел для их маркировки (по индексам i*p ) - это суть этого алгоритма. Только его работа до известного заранее предела, ограничивающего его сверху, обеспечивает этому алгоритму его линейность.
Сложность алгоритма на практике
Решето Эратосфена является популярным способом оценки производительности компьютера.<ref name="peng1985fall">Шаблон:Cite news</ref> Как видно из вышеизложенного доказательства сложности алгоритма, избавившись от константы и слагаемого очень близкого к нулюШаблон:Math, временная сложность вычисления всех простых чисел меньше Шаблон:Mvar аппроксимируется следующим соотношением Шаблон:Math. Однако алгоритм имеет экспоненциальную временную сложность в отношении размера входных данных, что делает его псевдополиномиальным алгоритмом. Памяти же для базового алгоритма требуется Шаблон:Math.<ref name="Pritchard1">Paul Pritchard, A sublinear additive sieve for finding prime numbers, Communications of the ACM 24 (1981), 18-23. Шаблон:MR</ref>
Сегментированная версия имеет ту же операционную сложность Шаблон:Math,<ref name="автоссылка2" />. что и несегментированная версия, но уменьшает потребность в используемой памяти до размера сегмента (размер сегмента значительно меньше размера всего массива простых чисел), который равен Шаблон:Math.<ref name="Pritchard3">Paul Pritchard, Fast compact prime number sieves (among others), Journal of Algorithms 4 (1983), 332—344. Шаблон:MR</ref> Также существует очень редко встречающееся на практике оптимизированное сегментированное решето Эратосфена. Оно строится за Шаблон:Math операций и занимает Шаблон:Math бит в памяти.<ref name="Pritchard1" /><ref name="Pritchard3" /><ref name="Pritchard2">Paul Pritchard, Explaining the wheel sieve, Acta Informatica 17 (1982), 477—485. Шаблон:MR</ref>
На практике оказывается, что оценка Шаблон:Math не очень точна даже для максимальных практических диапазонов таких как 1016.<ref name="Pritchard2" /> Ознакомившись с вышеописанным доказательством сложности, нетрудно понять откуда взялась неточность оценки. Расхождение с оценкой можно объяснить следующим образом: в пределах данного практического диапазона просеивания существенное влияние оказывают постоянные смещения.<ref name="автоссылка2" /> Таким образом очень медленно растущий член Шаблон:Math не становится достаточно большим, чтобы константами можно было справедливо пренебречь, до тех пор пока Шаблон:Mvar не приблизится к бесконечности, что естественно выходит за границы любого прикладного диапазона просеивания.<ref name="автоссылка2" /> Данный факт показывает, что для актуальных на сегодняшний день входных данных производительность решета Эратосфена намного лучше, чем следовало ожидать, используя только асимптотические оценки временной сложности.<ref name="Pritchard2" />
Решето Эратосфена работает быстрее, чем часто сравниваемое с ним решето Аткина только для значений Шаблон:Mvar меньших 10 10 .<ref name="автоссылка5">Шаблон:Статья</ref> Сказанное справедливо при условии, что операции занимают примерно одно и то же время в циклах центрального процессора, а это является разумным предположением для одного алгоритма, работающего с огромным битовым массивом.<ref name="автоссылка6">Шаблон:Статья</ref> С учётом этого предположения получается, что сито Аткина быстрее чем максимально факторизованное решето Эратосфена для Шаблон:Mvar свыше 10 13 , но при таких диапазонах просеивания потребуется занять огромное пространство в оперативной памяти, даже если была использована «битовая упаковка».<ref name="автоссылка6" /> Однако раздел о сегментированной версии решета Эратосфена показывает, что предположение о сохранении равенства во времени, затрачиваемом на одну операцию, между двумя алгоритмами не выполняется при сегментации.<ref name="автоссылка4" /><ref name="автоссылка5" /> В свою очередь это приводит к тому, что решето Аткина (несегментированное) работает медленнее, чем сегментированное решето Эратосфена с увеличением диапазона просеивания, за счёт уменьшения времени на операцию для второго.
Использование нотации Шаблон:Math большого также не является правильным способом сравнения практических характеристик даже для вариаций решета Эратосфена, поскольку данная нотация игнорирует константы и смещения, которые могут быть очень значительными для прикладных диапазонов.<ref name="автоссылка2" /> Например, одна из вариаций решета Эратосфена известная как решето Притчарда<ref name="Pritchard1" /> имеет производительность Шаблон:Math,<ref name="Pritchard2" /> но её базовая реализация требует либо алгоритма «одного большого массива»<ref name="Pritchard3" /> (то есть использования обычного массива, в котором хранятся все числа до Шаблон:Math), который ограничивает его диапазон использования до объёма доступной памяти, либо он должен быть сегментирован для уменьшения использования памяти. Работа Притчарда уменьшила требования к памяти до предела, но платой за данное улучшение по памяти является усложнение вычислений, что приводит увеличению операционной сложности алгоритмов.<ref name="Pritchard2" />
Популярным способом ускорения алгоритмов, работающих с большими массивами чисел, является разного рода факторизация.<ref name="автоссылка7">Шаблон:Статья</ref> Применение методов факторизации даёт значительное уменьшение операционной сложности за счёт оптимизации входного массива данных.<ref name="автоссылка7" /><ref name="автоссылка1">Шаблон:Статья</ref> Для индексных алгоритмов часто используют кольцевую факторизацию.<ref name="автоссылка1" /><ref>Шаблон:Статья</ref> Рассматриваемые в данной статье алгоритмы нахождения всех простых чисел до заданного Шаблон:Math подобные решету Эратосфена относятся к индексным, что позволяет применять к ним метод кольцевой факторизации.<ref>Шаблон:Статья</ref>
Несмотря на теоретическое ускорение, получаемое с помощью кольцевой факторизации, на практике существуют факторы, которые не учитываются при расчётах, но способны оказать существенное влияние на поведение алгоритма, что в результате может не дать ожидаемого прироста в быстродействии.<ref>Шаблон:Статья</ref> Рассмотрим наиболее существенные из них:
- Шаблон:Math При аналитических расчётах предполагается, что скорость выполнения арифметических операций равноценна. Но на самом деле это не так, и умножение, и деление выполняются гораздо медленнее, чем сложение и вычитание. Таким образом данный фактор никак не влияет на решето Эратосфена, поскольку оно использует только сложение и вычитание, но является весьма существенным для решета Питчарда (один из результатов усложнения вычислений упомянутого выше).<ref>Шаблон:Статья</ref>
- Шаблон:Math Компилятор оптимизирует на стадии компиляции все программы для более корректного исполнения машиной. Но часто бывает очень сложно сказать, какой вклад даёт данная оптимизация, и будет ли этот вклад одинаковым для двух различных алгоритмов.<ref name="автоссылка3">Шаблон:Статья</ref>
- Шаблон:Math Процессор использует кэш, чтобы ускорить извлечение инструкций и данных из памяти. Наличие кэша приводит к тому, что программы, использующие локализованные ссылки, будут работать быстрее. Но алгоритмы просеивания простых чисел, которые используют факторизацию высокой степени, часто генерируют случайные ссылки в память, что снижает их производительность.<ref name="автоссылка3" />
Для наглядности представления вклада факторизации в производительность алгоритмов просеивания ниже приведены две таблицы. В таблицах приведены результаты измерения реального времени исполнения решета Эратосфена и решета Питчарда в секундах для разных диапазонов Шаблон:Math и разных степеней кольцевой факторизации. Шаблон:Math и Шаблон:Math обозначения для решета Эратосфена и Питчарда соответственно, где индекс Шаблон:Math означает степень кольцевой факторизации. Шаблон:Math и Шаблон:Math означают отсутствие факторизации.<ref name="автоссылка3" />
| Шаблон:Mvar | Шаблон:Math | Шаблон:Math | Шаблон:Math | Шаблон:Math | Шаблон:Math | Шаблон:Math |
|---|---|---|---|---|---|---|
| 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 |
Из таблицы видно, что лучшую производительность имеет решето Эратосфена со средней степенью факторизации Шаблон:Math. Данный факт можно объяснить влиянием кэш-фактора, рассмотренного выше, на алгоритмы с высокой степенью факторизации.
| Шаблон:Mvar | Шаблон:Math | Шаблон:Math | Шаблон:Math | Шаблон:Math | Шаблон:Math | Шаблон:Math |
|---|---|---|---|---|---|---|
| 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 |
С увеличением Шаблон:Math соотношение времен становится всё больше в пользу решета Эратосфена, а на диапазоне Шаблон:Math = 5000000 оно стабильно быстрее при любых факторизациях. Данный факт ещё раз подтверждает проигрыш в быстродействии решета Питчарда из-за сложных вычислений.<ref name="Pritchard2" />