§ 4.6. Решето Эратосфена

Решето Эратосфена — это старейший из известных способов выписывания простых чисел. В отличие от методов, обсуждавшихся в предыдущих параграфах, он не использует никакой специальной функции. Эратосфен (Erathostenes) был греческим математиком, родившимся около 284 года до н. э. Он владел многими отраслями знаний, однако современники не считали его выдающимся специалистом ни в одной из них. Они прозвали его «Бета» (вторая буква греческого алфавита) и «Пентатлосом». Вот уже 2300 лет мы пользуемся его работами, а полученные им прозвища являются лишним подтверждением величия древнегреческой математики.

В своей «Арифметике», опубликованной около 100 года н. э., Никомах из Герасы (Nicomachus of Gerasa) вводит решето Эратосфена следующим образом:

«Метод для получения этих [простых чисел] называется по Эратосфену решетом, так как мы берем все нечетные числа, смешанные беспорядочно вместе, и выбрасывая из них, как неким инструментом, или решетом, мы отделяем в первую очередь неразложимые, а во вторую составные посредством их самих.»

Для дальнейшего знакомства с высказыванием Никомаха о решете смотри [47].

Итак, решето получило свое имя потому, что когда оно применяется к списку натуральных чисел, составные числа просеиваются, а простые задерживаются. Посмотрим, как оно работает.

Прежде всего, цель решета — определить все положительные простые числа, меньшие некоторой верхней границы

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

Теперь мы начинаем просеивать список. Первое число в нем 3. Начиная со следующего числа в списке (это 5), мы вычеркиваем из него каждое третье число. Проделав это до конца, мы вычеркнем все числа из списка, кратные 3 и большие самой тройки.

Теперь выберем наименьшее число из списка, превосходящее 3, которое еще не было вычеркнуто. Таким будет 5, а следующее за ним число — 7. Вычеркиваем каждое пятое число из нашего списка, начиная с 7. Таким образом, все числа, кратные 5, будут вычеркнуты. Продолжаем эту процедуру, пока не дойдем до Заметим, что если мы собираемся вычеркивать каждое число, то всегда надо начинать отсчет с числа даже когда это число было вычеркнуто на предыдущих шагах.

Например, для список нечетных чисел выглядит так:

Вычеркнув каждое третье число начиная с 5, мы получим

Теперь мы вычеркиваем каждое пятое число, начиная с 7, что дает

Мы должны бы теперь вычеркнуть каждое седьмое число, начиная с 9. Но если мы это сделаем, то никакие новые числа

не отсеются. Далее нам нужно бы вычеркнуть каждое одиннадцатое число, начиная с 13, но это опять не даст никакого эффекта. На самом деле, ни одно из чисел, оставшихся в списке после вычеркивания каждого пятого, не будет позже вычеркнуто ни на каком этапе просеивания. Итак, положительные нечетные простые числа, не превосходящие 41, это

В разобранном примере есть пара важных обстоятельств, которые нужно взять на заметку. Во-первых, хотя нам следовало повторять процесс вычеркивания вплоть до граничного числа (41 в нашем примере), мы избавились от всех составных чисел к тому моменту, когда отсеяли кратные 5, и все остальные просеивания оказались излишними. Во-вторых, некоторые числа вычеркивались больше, чем один раз. Такое произошло, например, с 15. Первый раз оно было вычеркнуто, когда мы отсеивали кратные 3. Но 15 также делится на 5, поэтому оно было вычеркнуто снова при отсеивании кратных 5.

Посмотрим, как можно увеличить эффективность решета в свете этих двух замечаний. Начнем со второго из них, т.е. посмотрим, можем ли мы так все организовать, чтобы каждое число вычеркивалось только один раз? К сожалению, ответ на этот вопрос отрицателен: нет хорошего способа добиться этого. Хотя кое-что в указанном направлении сделать все-таки можно.

Предположим, что мы отсеиваем числа, кратные какому-то простому Учитывая наше описание решета, нам следовало бы вычеркивать каждое число, начиная с следующего за числа в списке. Простейшее усовершенствование — это начинать процесс вычеркивания не с а с наименьшего числа, кратного которое не делится на простое число, меньшее Найдем его. Положительные числа, кратные записываются в виде где k — натуральное. Если то делится на число, меньшее а именно на к. Значит, первое

кратное число, которое не делится на простое число, меньшее есть Так что достаточно вычеркивать каждое число, начиная с Однако необходимо обратить внимание на то, что даже после этого нововведения останутся числа, которые будут вычеркиваться не единожды.

Что касается другого замечания, можем ли мы закончить отсев раньше, чем дойдем до шага? На этот раз ответ положителен, он следует того, что мы только что сделали. Допустим, например, что мы вычеркиваем каждое число. Как мы только что видели, первое число, подлежащее вычеркиванию, равно Но если такого числа нет в списке и мы можем забыть о нем. В итоге, нам нужно вычеркивать каждое до тех пор, пока Поскольку целое, это равносильно тому, что В примере, разобранном выше, Вот почему отбрасывание кратных 3 и 5 было достаточно для вылавливания всех составных чисел из списка.

Сейчас мы должны обсудить компьютерную реализацию решета. Список нечетных чисел представляется одномерным массивом, который также принято называть вектором. Напомним, что с каждой ячейкой вектора ассоциируется два числа. Одно из них — значение ячейки, а другое идентифицирует ее местоположение в векторе. Например, в векторе

величина ячейки, отмеченной стрелкой, равна а ее индекс — двум, поскольку она стоит на втором месте в векторе.

Вернемся к решету Эратосфена. Предположим, что мы хотим найти все простые числа, не превосходящие нечетного целого Сначала мы должны построить вектор с ячейками, по одной для каждого нечетного целого Ячейки будут принимать одно из двух возможных значений: 1 или 0. Если значение ячейки равно 0, то нечетное число, ею

представленное, было вычеркнуто на каком-то предыдущем шаге процесса просеивания. Итак, начальное значение каждой ячейки равно 1, поскольку еще нет никаких вычеркнутых чисел. Чтобы «вычеркнуть» число нужно заменить 1, стоящую в ячейке вектора, на 0. Конечно, эта ячейка могла быть «вычеркнута» на предыдущем шаге решета. В этом случае ее значение уже равно 0 и не будет меняться в процессе выполнения следующих шагов алгоритма.

Теперь мы приведем более или менее подробную версию алгоритма для решета Эратосфена, который был описан выше. Она содержит оба усовершенствования, которые мы обсуждали, т.е. каждое число вычеркивается начиная с а алгоритм заканчивается, как только превысит

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

Ввод: нечетное натуральное

Вывод: список всех нечетных положительных простых чисел, меньших или равных

Шаг 1. Начинаем с создания вектора ячейками, каждой из которых присвоено значение 1, и полагаем

Шаг 2. Если выписываем все числа для которых значение ячейки вектора равно 1 и останавливаемся; в противном случае переходим к шагу 3.

Шаг 3. Если значение ячейки вектора с номером равно 0, увеличиваем на 2 и возвращаемся к шагу 2; в противном случае переходим к шагу 4.

Шаг 4. Присваиваем новой переменной значение замещаем нулем значение ячейки вектора под номером и увеличиваем на повторяем эти два шага до тех пор, пока затем увеличиваем на 2 и возвращаемся к шагу 2.

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

каждое число, то число, которое будет вычеркнуто после есть

Вам может показаться, что существует простое изменение описанной выше процедуры, которое ускорит алгоритм. Способ, с помощью которого мы избавляемся от нежелательных составных чисел в векторе, состоит в замене 1, стоящей в соответствующей ячейке, на 0. Но почему, если мы не заботимся о составных числах, просто не выбросить их из вектора? К сожалению, мы не можем этого сделать. Неприятность в том, что метод, которым мы узнаем кратно ли число, соответствующее данной ячейке, некоторому зависит от номера ячейки. Другими словами, числа, кратные встречаются в каждой позиции вектора. Если мы удалим некоторые числа из списка, то алгоритм, который мы описали, перестанет работать.

Подобно всем алгоритмам, решето Эратосфена имеет ограничения. Например, оно неэффективно при поиске очень больших простых чисел. Напомним, однако, что цель этого алгоритма — поиск всех простых меньших, чем определенная верхняя граница. Ясно, что такой поиск невыполним, если граница слишком велика.

Суммируя ограничения, накладываемые назначением алгоритма, отметим два его слабых места: решето требует уйму компьютерной памяти и должно проделать слишком много витков цикла. К его достоинствам можно отнести простоту программирования и, кроме того, нам не нужно вычислять отдельные делители.

Упражнения

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)