Что такое решето Эратосфена

Введение

Решетом Эратосфена назван разработанный им алгоритм, который позволяет найти все простые числа вплоть до заданного целого числа n. Как это часто бывает, в названии алгоритма заложен принцип его функционирования. Термин решето имеет в виду фильтр, который пропускает все числа кроме простых. Список всех чисел фильтруется и при этом ненужные, составные числа отсеиваются, а искомые простые числа оставляются. Метод, как гласит легенда, был назван решетом, поскольку Эратосфен использовал для записи чисел дощечку, которая была покрыта воском, и он делал отверстия там, где писал составные числа. Эта доска стала аналогом решета, через которое отсеивались только составные числа, а простые, естественно, не отсеивались. Эратосфенам была составлена таблица простых чисел вплоть до тысячи.

Алгоритм решето Эратосфена

Чтобы найти все простые числа вплоть до некоторого числа n согласно способу Эратосфена, необходимо осуществить такие действия:

1. Записать в целочисленный ряд все числа, начиная от двойки и заканчивая n (2, 3, 4, …, n).
2. Предположим, что некая переменная р сначала равняется двум (это первое простое число).
3. Далее необходимо выполнить зачёркивание чисел от 2р до n, отсчитывая шагами, равными р. То есть это числовой ряд, кратных р значений: 2р, 3р, 4р, …).
4. Затем нужно выполнить поиск первого не зачёркнутого числа в списке, большего чем р, и назначить переменной р это числовое значение.
5. Далее необходимо выполнять повторение этапов три и четыре до тех пор, пока это ещё можно сделать.

После завершения этого алгоритма, список будет состоять только из простых чисел от двух до n, имея в виду только те числа, которые не зачёркнуты. При практической реализации, возможны следующие улучшения алгоритма. В пункте номер три возможно выполнять зачёркивание чисел, начав сразу с $p^2$, поскольку составные числа, которые меньше этого числа, к этому моменту будут уже зачёркнуты. И, следовательно, прекращать работу алгоритма можно, когда $p^2$ примет значение большее, чем n. И кроме того, все простые числа, исключая двойку, являются нечётными числами, и значит для них начинать отсчёт шагов по 2р возможно, начиная с $p^2$.

Рассмотрим конкретный пример выполнения этого алгоритма для 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

Первым в списке стоит простое число два. Выполним проход по числовому ряду и будем зачёркивать все кратные двум числа. Фактически это будет каждое второе число, начиная с четвёрки, поскольку это два в квадрате:

Рисунок 1. Числовой ряд. Автор24 — интернет-биржа студенческих работ

Следующим не зачёркнутым числом будет простое число три. Выполним проход по числовому ряду и зачеркнём все кратные трём числа. А именно каждое третье число, начиная с девятки, поскольку три в квадрате это девять:

Рисунок 2. Числовой ряд. Автор24 — интернет-биржа студенческих работ

Очередным не зачёркнутым числом теперь будет простое число пять. Выполним проход по числовому ряду и зачеркнём все числа, которые кратны пяти. А именно каждое пятое число, начав с двадцати пяти, поскольку это пять в квадрате:

Рисунок 3. Числовой ряд. Автор24 — интернет-биржа студенческих работ

Далее очередным не зачёркнутым числом будет семёрка. Но семь в квадрате это сорок девять, что уже больше тридцати. Значит действие алгоритма закончено и все не простые числа мы уже зачеркнули:

2 3 5 7 11 13 17 19 23 29

Модифицированные варианты решета Эратосфена

Существует версия решета Эратосфена, которая называется неограниченным или постепенным вариантом. Здесь вычисление простых чисел осуществляется последовательно, без верхнего ограничения. Определяются числа, которые находятся в интервалах между составными числами, найденными для всех простых чисел р, начиная с р в квадрате и с шагом р (или 2р, если это нечётные простые числа). Алгоритм может быть представлен в следующем виде:

Рисунок 4. Алгоритм. Автор24 — интернет-биржа студенческих работ

Здесь \ является обозначением разницы среди арифметических прогрессий. Первым простым числом является двойка, что заранее определено, поэтому нет никаких логических ошибок.

Решето Эратосфена иногда могут спутать с алгоритмами поэтапной фильтрации составных чисел, где выполняется тестирование каждого числа, подозреваемого в не простоте, применяя одно простое число на каждом шаге. Одним из таких вариантов является очень популярный функциональный код Дэвида Тёрнера, который часто путают с решетом Эратосфена. Но фактически это не оптимизированный вариант, основанный на переборе делителей. В псевдокоде он записывается так:

Рисунок 5. Псевдокод. Автор24 — интернет-биржа студенческих работ