29-08-2023
Решето́ Эратосфе́на — алгоритм нахождения всех простых чисел до некоторого целого числа n, который приписывают древнегреческому математику Эратосфену Киренскому.
Содержание |
Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:
Теперь все не зачеркнутые числа в списке — простые.
На практике, алгоритм можно несколько улучшить следующим образом. На шаге № 3, числа можно зачеркивать, начиная сразу с числа , потому что все составные числа меньше его уже будут зачеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда станет больше, чем .[1]
Можно показать, что сложность алгоритма составляет операций в модели вычислений RAM, или битовых операций,[2][3] при условии вычисления и зачеркивания каждого кратного числа за время , например при использования массивов с прямым доступом.
В этом варианте простые числа вычисляются последовательно, без ограничения сверху, как числа находящиеся в промежутках между составными числами, которые вычисляются для каждого простого числа 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, являются простыми.
Запишем натуральные числа начиная от 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)-го простого числа. Все числа в списке, меньшие квадрата его первого числа, являются простыми.
Решето Эратосфена.