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

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

Алгоритм

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

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

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

На практике, алгоритм можно несколько улучшить следующим образом. На шаге № 3, числа можно зачеркивать, начиная сразу с числа $p^2$, потому что все составные числа меньше его уже будут зачеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда $p^2$ станет больше, чем $n$.^[1]

Можно показать, что сложность алгоритма составляет $O(n \log \log n)$ операций в модели вычислений RAM, или $O(n (\log n) (\log \log n))$ битовых операций,^[2][3] при условии вычисления и зачеркивания каждого кратного числа за время $O(1)$, например при использования массивов с прямым доступом.

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

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

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

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

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

Псевдокод

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

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

 для i := 2, 3, 4, ..., пока i^2 ≤ n:
  если A[i] = true:
    для j := i^2, i^2 + i, i^2 + 2i, ..., пока j ≤ n:
      если A[j] = true:
        A[j] := false

Теперь все числа i, такие что A[i] = true, являются простыми.

Пример для $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

Необходимо провести зачёркивание кратных для всех простых чисел p, для которых p² ≤ n. В результате все составные числа будут зачеркнуты, а незачеркнутыми останутся все простые числа. Для n = 30 уже после зачёркивания кратных числу 5 все составные числа получаются зачеркнутыми:

 2  3     5     7           11    13          17    19          23                29   

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

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

Составляется исходный список начиная с числа 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)-го простого числа. Все числа в списке, меньшие квадрата его первого числа, являются простыми.

См. также

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

Примечания

1. ↑ ^{1 2} 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.
2. ↑ Pritchard, Paul, "Linear prime-number sieves: a family tree, " Sci. Comput. Programming 9:1 (1987), pp. 17—35.
3. ↑ ^{1 2 3} O'Neill, Melissa E., "The Genuine Sieve of Eratosthenes", Journal of Functional Programming, Published online by Cambridge University Press 9 October 2008 doi:10.1017/S0956796808007004
4. ↑ ^{1 2} Colin Runciman, "FUNCTIONAL PEARL: Lazy wheel sieves and spirals of primes", Journal of Functional Programming, Volume 7 Issue 2, March 1997; также здесь.
5. ↑ Turner, David A. SASL language manual. Tech. rept. CS/75/1. Department of Computational Science, University of St. Andrews 1975.