Решето́ Эратосфе́на — алгоритм нахождения всех простых чисел до некоторого целого числа , который приписывают древнегреческому математику Эратосфену КиренскомуНикомах Герасский, Введение в арифметику, I, XIII, 2. по-гречески, по-русски . Название алгоритма говорит о принципе его работы: алгоритм осуществляет
списка чисел от 2 до . По мере прохождения списка составные числа исключаются, а простые остаются.
История
Этот метод описан во «Введении в арифметику» Никомаха Герасского. Никомах называет автором метода Эратосфена. То же делает и Ямвлих в своём комментарии к этому сочинению Никомаха.
Название «решето» метод получил потому, что во времена Эратосфена писали числа на дощечке, покрытой воском, и прокалывали дырочки в тех местах, где были написаны составные числа. Поэтому дощечка являлась неким подобием решета, через которое «просеивались» все составные числа, а оставались только числа простые.
Никомах, во II веке н. э., объясняет, что метод решета «высеивает» простые числа из нечётных, отделяя от них составные числа, которые он находит, перечисляя для каждого нечетного числа n все его кратные числа как каждое n-ное число в ряду нечётных чисел, начиная с n. Число 2 он здесь не рассматривал, так как в качестве возможно простых чисел он рассматривал только нечётные.
Символически, используя знак " " как «разность множеств», его весьма многословное словесное описание выражает алгоритм
Primes = {3,5,7,9,...} \ Composites
Composites = { 3n,5n,7n,9n,... for n in {3,5,7,9,...} }где каждая последовательность "3n,5n,7n,9n ..." находится прямым перечислением как указано выше, без умножений.
Британец , 16 веков спустя, горячо критикует это описание, заявляя что «истинный» метод Эратосфена «наверняка» был «гораздо умнее», начиная перечисление кратных с квадратов самих простых чисел прямо в процессе их распознавания:
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. Кроме того, все простые числа, кроме 2, — нечётные числа, и поэтому для них можно считать шагами по 2p, начиная с p2.
Пример для 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
Первое число в списке, — простое. Пройдём по ряду чисел, зачёркивая все числа, кратные (то есть, каждое второе, начиная с ):
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 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 (то есть, каждое пятое, начиная с ):
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 3 5 7 11 13 17 19 23 29
Псевдокод Оптимизированная реализация (начинающаяся с квадратов) на псевдокоде, p. 16.Jonathan Sorenson, An Introduction to Prime Number Sieves , 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).:
Вход: натуральное число 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.
Сложность алгоритма Сложность алгоритма составляет операций при составлении таблицы простых чисел до Pritchard, Paul, "Linear prime-number sieves: a family tree, " Sci. Comput. Programming 9:1 (1987), pp. 17-35..
Доказательство сложности При выбранном для каждого простого будет выполняться внутренний циклСтрого говоря, внутренний цикл выполняется для каждого простого , но = , поэтому, традиционно, для краткости, квадратный корень опускают., который совершит действий. Сложность алгоритма можно получить из оценки следующей величины:
Так как количество простых чисел, меньших либо равных , оценивается как , и, как следствие, -е простое число примерно равно , то сумму можно преобразовать:
Здесь из суммы выделено слагаемое для первого простого числа, чтобы избежать деления на ноль. Данную сумму можно оценить интегралом
В итоге получается для изначальной суммы:
Более строгое доказательство (и дающее более точную оценку с точностью до константных множителей) можно найти в книге Hardy и Wright «An Introduction to the Theory of Numbers»Hardy and Wright "An Introduction to the Theory of Numbers, p. 349.
Модификации метода
Неограниченный, постепенный вариант В этом варианте простые числа вычисляются последовательно, без ограничения сверху,O’Neill, Melissa E., «The Genuine Sieve of Eratosthenes» , Journal of Functional Programming, Published online by Cambridge University Press 9 October 2008 . как числа, находящиеся в промежутках между составными числами, которые вычисляются для каждого простого числа , начиная с его квадрата, с шагом в (или для нечетных простых чисел )Horsley, Rev. Samuel, F. R. S., " 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 .. Может быть представлен абстрактно в парадигме потоков данных как
primes = {2,3,...} \ { p², p²+p, ... for p in primes }
используя нотацию абстракции списков, где \ обозначает разницу между арифметическими прогрессиями.
Первое простое число (среди возрастающих положительных целых чисел) заранее известно, поэтому в этом самореферентном определении нет порочного круга.
Более конкретный псевдокод с поэтапным отсеиванием, в неэффективной реализации, для простоты сравнения с нижеследующими вариантами: 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..])]
Перебор делителей Решето Эратосфена часто путают с алгоритмами, которые поэтапно составные числа, тестируя каждое из чисел-кандидатов на делимость по одному простому числу на каждом этапе.Colin Runciman, «FUNCTIONAL PEARL: Lazy wheel sieves and spirals of primes», Journal of Functional Programming, Volume 7 Issue 2, March 1997; также здесь .
Широко известный функциональный код Дэвида Тёрнера 1975 г.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) часто принимают за решето Эратосфена, но на самом деле это неоптимальный вариант с перебором делителей: primes = sieve [2..] where sieve [p, ...xs] = [p, ...sieve [x in xs if x%p > 0]] В оптимальном варианте не используются делители, большие квадратного корня тестируемого числа.
Сегментированное решето Как замечает Соренсон, главной проблемой реализации решета Эратосфена на вычислительных машинах является не количество выполняемых операций, а требования по объёму занимаемой памяти (впрочем, его замечание относится к неактуальному сейчас компьютеру DEC VAXstation 3200, выпущенному в 1989 году). При больших значениях , диапазон простых чисел может превысить доступную память; хуже того, даже при сравнительно небольших использование кэша памяти далеко от оптимального, так как алгоритм, проходя по всему массиву, нарушает принцип .
Для решения представленной проблемы используется сегментированное решето, в котором за итерацию просеивается только часть диапазона простых чисел.Crandall & Pomerance, Prime Numbers: A Computational Perspective, second edition, Springer: 2005, pp. 121-24. Данный метод известен с 1970-х годов и работает следующим образом:
Разделяем диапазон от 2 до на отрезки (сегменты) некоторой длины . Находим все простые числа в первом отрезке, используя обычное решето. Каждый из последующих отрезков оканчивается на некотором числе . Находим все простые числа в отрезке следующим образом: Создаем булевый массив размера Для каждого простого числа из уже найденных, отмечаем в массиве как «непростые» все числа кратные , перебирая числа с шагом в , начиная с наименьшего кратного числа в данном отрезке.
Если число выбрано равным , то сложность алгоритма по памяти оценивается как , а операционная сложность остаётся такой же, что и у обычного решета Эратосфена.
Для случаев, когда настолько велико, что все просеиваемые простые числа меньшие не могут уместиться в памяти, как того требует алгоритм сегментированного сита, используют более медленные, но с гораздо меньшими требованиями по памяти алгоритмы, например решето Соренсона.J. Sorenson, The pseudosquares prime sieve , Proceedings of the 7th International Symposium on Algorithmic Number Theory. (ANTS-VII, 2006).
Решето Эйлера Доказательство тождества Эйлера для дзета-функции Римана содержит механизм отсеивания составных чисел подобный решету Эратосфена, но так, что каждое составное число удаляется из списка только один раз. Схожее решето описано в Gries & Misra 1978 г. как решето с линейным временем работы (см. ниже).
Составляется исходный список начиная с числа . На каждом этапе алгоритма первый номер в списке берется как следующее простое число, результаты произведения которого на каждое число в списке помечаются для последующего удаления. После этого из списка убирают первое число и все помеченные числа, и процесс повторяется вновь:
(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 ... (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 ... (7) 11 13 17 19 23 29 31 37 41 43 47 49 53 59 61 67 71 73 77 79 ... (11) 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 ... [...]
Здесь показан пример начиная с нечетных чисел, после первого этапа алгоритма. Таким образом, после -го этапа рабочий список содержит только числа взаимно простые с первыми простыми числами (то есть числа не кратные ни одному из первых простых чисел), и начинается с -го простого числа. Все числа в списке, меньшие квадрата его первого числа, являются простыми.
В псевдокоде,
primes = sieve [2..] where sieve [p, ...xs] = [p, ...sieve (xs \ [p², ...p*xs])]
Решето только по нечётным числам