Решето ЭратосфенаРешето́ Эратосфе́на — алгоритм нахождения всех простых чисел до некоторого целого числа n, который приписывают древнегреческому математику Эратосфену Киренскому[1]. Название алгоритма говорит о принципе его работы: алгоритм осуществляет фильтрацию списка чисел от 2 до n. По мере прохождения списка составные числа исключаются, а простые остаются. ИсторияЭтот метод описан во «Введении в арифметику» Никомаха Герасского. Никомах называет автором метода Эратосфена. То же делает и Ямвлих в своём комментарии к этому сочинению Никомаха. Название «решето» метод получил потому, что во времена Эратосфена писали числа на дощечке, покрытой воском, и прокалывали дырочки в тех местах, где были написаны составные числа. Поэтому дощечка являлась неким подобием решета, через которое «просеивались» все составные числа, а оставались только числа простые[4]. Никомах, во II веке н. э., объясняет, что метод решета «высеивает» простые числа из нечётных, отделяя от них составные числа, которые он находит, перечисляя для каждого нечетного числа n каждое n-ное число в ряду нечётных чисел, начиная с n. Число 2 он здесь не рассматривал, так как в качестве возможно простых чисел он рассматривал только нечётные[1]. Символически, используя знак " \ " как «разность множеств», его весьма многословное словесное описание выражает алгоритм Primes = {3,5,7,9,...} \ Composites Composites = { 3n,5n,7n,9n,... for n in {3,5,7,9,...} } Британец Хорсли[англ.], 16 веков спустя, горячо критикует это описание, заявляя что «истинный» метод Эратосфена «наверняка» был «гораздо умнее», начиная с квадратов самих простых чисел прямо в процессе их распознавания[3]: Primes = {3,5,7,9,...} \ Composites Composites = { n²,n²+2n,n²+4n,... for n in Primes } АлгоритмДля нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:
Теперь все незачёркнутые числа в списке — это все простые числа от 2 до n. На практике, алгоритм можно улучшить следующим образом. На шаге № 3 числа можно зачеркивать, начиная сразу с числа p2, потому что все меньшие числа, кратные p, обязательно имеют простой делитель меньше p, и они уже будут зачеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда p2 станет больше, чем n.[3] Кроме того, все простые числа, кроме 2, — нечётные числа, и поэтому для них можно считать шагами по 2p, начиная с p2. Пример для 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 (то есть, каждое второе, начиная с 22 = 4): 2 3 Следующее незачеркнутое число, 3 — простое. Пройдём по ряду чисел, зачёркивая все числа, кратные 3 (то есть, каждое третье, начиная с 32 = 9): 2 3 Следующее незачеркнутое число, 5 — простое. Пройдём по ряду чисел, зачёркивая все числа, кратные 5 (то есть, каждое пятое, начиная с 52 = 25): 2 3 Следующее незачеркнутое число — 7. Его квадрат, 49 — больше 30, поэтому на этом работа завершена. Все составные числа уже зачеркнуты: 2 3 5 7 11 13 17 19 23 29 ПсевдокодОптимизированная реализация (начинающаяся с квадратов) на псевдокоде[5][6]: Вход: натуральное число 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. Сложность алгоритмаСложность алгоритма составляет операций при составлении таблицы простых чисел до [7]. Доказательство сложностиПри выбранном для каждого простого будет выполняться внутренний цикл[8], который совершит действий. Сложность алгоритма можно получить из оценки следующей величины:
Так как количество простых чисел, меньших либо равных , оценивается как , и, как следствие, -е простое число примерно равно , то сумму можно преобразовать:
Здесь из суммы выделено слагаемое для первого простого числа, чтобы избежать деления на ноль. Данную сумму можно оценить интегралом
В итоге получается для изначальной суммы:
Более строгое доказательство (и дающее более точную оценку с точностью до константных множителей) можно найти в книге Hardy и Wright «An Introduction to the Theory of Numbers»[9]. Модификации методаНеограниченный, постепенный вариантВ этом варианте простые числа вычисляются последовательно, без ограничения сверху,[10] как числа, находящиеся в промежутках между составными числами, которые вычисляются для каждого простого числа p, начиная с его квадрата, с шагом в p (или для нечетных простых чисел 2p)[3]. Может быть представлен абстрактно в парадигме потоков данных как 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..])] Перебор делителейРешето Эратосфена часто путают с алгоритмами, которые поэтапно отфильтровывают[англ.] составные числа, тестируя каждое из чисел-кандидатов на делимость по одному простому числу на каждом этапе.[11] Широко известный функциональный код Дэвида Тёрнера 1975 г.[12] часто принимают за решето Эратосфена,[11] но на самом деле[10] это неоптимальный вариант с перебором делителей: primes = sieve [2..] where sieve [p, ...xs] = [p, ...sieve [x in xs if x%p > 0]] В оптимальном варианте не используются делители, большие квадратного корня тестируемого числа. Сегментированное решетоКак замечает Соренсон, главной проблемой реализации решета Эратосфена на вычислительных машинах является не количество выполняемых операций, а требования по объёму занимаемой памяти (впрочем, его замечание относится к неактуальному сейчас компьютеру DEC VAXstation 3200, выпущенному в 1989 году).[6] При больших значениях n, диапазон простых чисел может превысить доступную память; хуже того, даже при сравнительно небольших n использование кэша памяти далеко от оптимального, так как алгоритм, проходя по всему массиву, нарушает принцип локализованности ссылок[англ.]. Для решения представленной проблемы используется сегментированное решето, в котором за итерацию просеивается только часть диапазона простых чисел.[13] Данный метод известен с 1970-х годов и работает следующим образом:[6][14]
Если число Δ выбрано равным √n, то сложность алгоритма по памяти оценивается как O(√n), а операционная сложность остаётся такой же, что и у обычного решета Эратосфена.[14] Для случаев, когда n настолько велико, что все просеиваемые простые числа меньшие √n не могут уместиться в памяти, как того требует алгоритм сегментированного сита, используют более медленные, но с гораздо меньшими требованиями по памяти алгоритмы, например решето Соренсона.[15] Решето ЭйлераДоказательство тождества Эйлера для дзета-функции Римана содержит механизм отсеивания составных чисел подобный решету Эратосфена, но так, что каждое составное число удаляется из списка только один раз. Схожее решето описано в 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, и т. д.. Уменьшение объёма потребляемой памятиАлгоритм Эратосфена фактически оперирует с битами памяти. Следовательно, можно существенно сэкономить потребление памяти, храня переменных булевского типа не как байт, а как бит, то есть байт памяти. Такой подход — «битовое сжатие» — усложняет оперирование этими битами. Любое чтение или запись бита будут представлять собой несколько арифметических операций. Но с другой стороны существенно улучшается компактность в памяти. Бо́льшие интервалы умещаются в кэш-память которая работает гораздо быстрее обычной так что при работе по-сегментно общая скорость увеличивается. Решето Эратосфена с линейным временем работыЭтот алгоритм находит составные числа как перечисление формулы { (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:
Утверждается, что таким образом каждое значение в lp[] назначается только один раз[16]. ПсевдокодВход: натуральное число 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. Сложность алгоритма на практикеРешето Эратосфена является популярным способом оценки производительности компьютера.[17] Как видно из вышеизложенного доказательства сложности алгоритма, избавившись от константы и слагаемого очень близкого к нулю (ln (ln n - ln ln n) - ln ln 2 ≈ ln ln n), временная сложность вычисления всех простых чисел меньше n аппроксимируется следующим соотношением O(n ln ln n). Однако алгоритм имеет экспоненциальную временную сложность в отношении размера входных данных, что делает его псевдополиномиальным алгоритмом. Памяти же для базового алгоритма требуется O(n).[18] Сегментированная версия имеет ту же операционную сложность O(n ln ln n),[9]. что и несегментированная версия, но уменьшает потребность в используемой памяти до размера сегмента (размер сегмента значительно меньше размера всего массива простых чисел), который равен O(√n/ln n).[19] Также существует очень редко встречающееся на практике оптимизированное сегментированное решето Эратосфена. Оно строится за O(n) операций и занимает O(√n ln ln n/ln n) бит в памяти.[18][19][20] На практике оказывается, что оценка ln ln n не очень точна даже для максимальных практических диапазонов таких как 1016.[20] Ознакомившись с вышеописанным доказательством сложности, нетрудно понять откуда взялась неточность оценки. Расхождение с оценкой можно объяснить следующим образом: в пределах данного практического диапазона просеивания существенное влияние оказывают постоянные смещения.[9] Таким образом очень медленно растущий член ln ln n не становится достаточно большим, чтобы константами можно было справедливо пренебречь, до тех пор пока n не приблизится к бесконечности, что естественно выходит за границы любого прикладного диапазона просеивания.[9] Данный факт показывает, что для актуальных на сегодняшний день входных данных производительность решета Эратосфена намного лучше, чем следовало ожидать, используя только асимптотические оценки временной сложности.[20] Решето Эратосфена работает быстрее, чем часто сравниваемое с ним решето Аткина только для значений n меньших 10 10 .[21] Сказанное справедливо при условии, что операции занимают примерно одно и то же время в циклах центрального процессора, а это является разумным предположением для одного алгоритма, работающего с огромным битовым массивом.[22] С учётом этого предположения получается, что сито Аткина быстрее чем максимально факторизованное решето Эратосфена для n свыше 10 13 , но при таких диапазонах просеивания потребуется занять огромное пространство в оперативной памяти, даже если была использована «битовая упаковка».[22] Однако раздел о сегментированной версии решета Эратосфена показывает, что предположение о сохранении равенства во времени, затрачиваемом на одну операцию, между двумя алгоритмами не выполняется при сегментации.[14][21] В свою очередь это приводит к тому, что решето Аткина (несегментированное) работает медленнее, чем сегментированное решето Эратосфена с увеличением диапазона просеивания, за счёт уменьшения времени на операцию для второго. Использование нотации O большого также не является правильным способом сравнения практических характеристик даже для вариаций решета Эратосфена, поскольку данная нотация игнорирует константы и смещения, которые могут быть очень значительными для прикладных диапазонов.[9] Например, одна из вариаций решета Эратосфена известная как решето Притчарда[18] имеет производительность O(n),[20] но её базовая реализация требует либо алгоритма «одного большого массива»[19] (то есть использования обычного массива, в котором хранятся все числа до n), который ограничивает его диапазон использования до объёма доступной памяти, либо он должен быть сегментирован для уменьшения использования памяти. Работа Притчарда уменьшила требования к памяти до предела, но платой за данное улучшение по памяти является усложнение вычислений, что приводит увеличению операционной сложности алгоритмов.[20] Популярным способом ускорения алгоритмов, работающих с большими массивами чисел, является разного рода факторизация.[23] Применение методов факторизации даёт значительное уменьшение операционной сложности за счёт оптимизации входного массива данных.[23][24] Для индексных алгоритмов часто используют кольцевую факторизацию.[24][25] Рассматриваемые в данной статье алгоритмы нахождения всех простых чисел до заданного n подобные решету Эратосфена относятся к индексным, что позволяет применять к ним метод кольцевой факторизации.[26] Несмотря на теоретическое ускорение, получаемое с помощью кольцевой факторизации, на практике существуют факторы, которые не учитываются при расчётах, но способны оказать существенное влияние на поведение алгоритма, что в результате может не дать ожидаемого прироста в быстродействии.[27] Рассмотрим наиболее существенные из них:
Для наглядности представления вклада факторизации в производительность алгоритмов просеивания ниже приведены две таблицы. В таблицах приведены результаты измерения реального времени исполнения решета Эратосфена и решета Питчарда в секундах для разных диапазонов n и разных степеней кольцевой факторизации. Ei и Pi обозначения для решета Эратосфена и Питчарда соответственно, где индекс i означает степень кольцевой факторизации. E0 и P0 означают отсутствие факторизации.[29]
Из таблицы видно, что лучшую производительность имеет решето Эратосфена со средней степенью факторизации E2. Данный факт можно объяснить влиянием кэш-фактора, рассмотренного выше, на алгоритмы с высокой степенью факторизации.
С увеличением n соотношение времен становится всё больше в пользу решета Эратосфена, а на диапазоне n = 5000000 оно стабильно быстрее при любых факторизациях. Данный факт ещё раз подтверждает проигрыш в быстродействии решета Питчарда из-за сложных вычислений.[20] См. такжеПримечания
Литература
Ссылки |