Решето Эратосфена
Решето́ Эратосфе́на — алгоритм нахождения всех простых чисел до некоторого целого числа n, который приписывают древнегреческому математику Эратосфену Киренскому.
Содержание |
[править] Алгоритм
Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:
- Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).
- Пусть переменная p изначально равна двум — первому простому числу.
- Считая от p шагами по p, зачеркнуть в списке все числа от 2p до n кратные p (то есть числа 2p, 3p, 4p, …)
- Найти первое не зачеркнутое число, большее чем p, и присвоить значению переменной p это число.
- Повторять шаги 3 и 4 до тех пор, пока p не станет больше, чем n
Теперь все не зачеркнутые числа в списке — простые.
На практике, алгоритм можно несколько улучшить следующим образом. На шаге № 3, числа можно зачеркивать, начиная сразу с числа p2, потому что все составные числа меньше его уже будут зачеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда p2 станет больше, чем n.[1]
Можно показать, что сложность алгоритма составляет O(nlog 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.
count := n - 1
для 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
count := count - 1
Теперь все числа i, такие что A[i] == true, являются простыми,
а переменная count содержит в себе их общее количество в массиве.
[править] Пример для 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 3456789101112131415161718192021222324252627282930
Следующее незачеркнутое число, 3 — простое. Пройдём по ряду чисел, зачёркивая все числа кратные 3 (то есть каждое третье, начиная с 32 = 9):
2 3456789101112131415161718192021222324252627282930
Следующее незачеркнутое число, 5 — простое. Пройдём по ряду чисел, зачёркивая все числа кратные 5 (то есть каждое пятое, начиная с 52 = 25). И т. д.
2 3456789101112131415161718192021222324252627282930
Необходимо провести зачёркивание кратных для всех простых чисел p, для которых p2 ≤ 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 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.
- ↑ Pritchard, Paul, "Linear prime-number sieves: a family tree, " Sci. Comput. Programming 9:1 (1987), pp. 17—35.
- ↑ 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
- ↑ 1 2 Colin Runciman, "FUNCTIONAL PEARL: Lazy wheel sieves and spirals of primes", Journal of Functional Programming, Volume 7 Issue 2, March 1997; также здесь.
- ↑ Turner, David A. SASL language manual. Tech. rept. CS/75/1. Department of Computational Science, University of St. Andrews 1975.
