Читатель без труда и довольно быстро может убедиться в том, что простыми числами, не превосходящими 100, являются: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.

Для получения этого ряда простых чисел нам пришлось выполнять процесс для р=2, р=3, р=5, р=7. Уже р=11 дало 112=121>100, что послужило сигналом для прекращения процесса. Как видит читатель, отбросив числа, делящиеся на первые 4 простых числа, мы получили 25 простых чисел, среди которых наибольшее 97.

В алгоритме Эратосфена мы встречаемся со случаем, в котором в процессе выполнения алгоритма получается очень большой промежуточный результат (последовательность n — 1 чисел, начинающаяся с числа 2). Слово «большой» здесь надо понимать в смысле числа символов, которые необходимо хранить в течение некоторого времени. Но это число для каждого n конечно, и потому алгоритм Эратосфена потенциально осуществим для любого n, хотя автор не советует читателю применять его к числу n =1 000 000 000 (1 млрд.). Не хватит ни бумаги, ни времени.

Как уже упоминалось, в простейших случаях алгоритмический процесс состоит из очень простых шагов. Но можно ли считать простым такой шаг, как выписывание последовательности n-1 чисел при больших значениях n? Или отсчитывание р чисел начиная с (р + 1)-го при больших значениях р? А ведь значения р могут быть как угодно велики (доказано, что среди простых чисел нет наибольшего. После каждого простого числа можно найти еще большее простое число).

Многие специалисты по теории алгоритмов считают, что такие шаги алгоритмического процесса недопустимы. С их точки зрения алгоритм Эратосфена не является алгоритмом, хотя и служит правилом для получения простых чисел. В чем же возражение против шагов, па которых могут преобразовываться объекты, состоящие хотя и из конечного, но не ограниченного числа символов? В том, что умственные способности исполнителя ограничены и поэтому ему доступны только операции ограниченной сложности. Возражение, конечно, резонное. Но для него существует и контрвозражение. Если мы абстрагируемся от ограниченности ресурсов времени и материалов (например, бумаги и карандашей), то почему бы не абстрагиро¬ваться и от ограниченности наших умственных ресурсов? Ведь можно создавать все более и более мощные вычислительные машины так, что благодаря их использованию с течением времени наши умственные способности будут совершенствоваться и когда-нибудь наступит такой момент, что алгоритмический процесс, который мы прежде не могли осуществить, станет легко осуществимым.

Автор считает это контрвозражение уважительным и не согласен с определением простоты действия, основанным на отрицании потенциальной возможности выполнять действия над объектами, образованными из сколь угодно большого (но конечного) числа символов. Если нам известен алгоритм, определяющий действие, то это действие потенциально осуществимо и поэтому нет никакого основания считать его слишком сложным. Другое дело, если какое-либо действие не является потенциально осуществимым. Но об этом речь будет впереди (см. § 1,гл. 8).

Ну, а как же с алгоритмом Эратосфена? Мы с вами, читатель, будем его признавать алгоритмом. А тем, кто с этим не согласится, предоставим право его преобразовать так, чтобы на каждом шагу выполнялось только очень простое действие. Это не очень трудно сделать. Выписывание последовательности чисел можно представить как выписывание отдельных цифр, получаемых с помощью алгоритма сложения, применяемого к числу 1 и цифрам последнего из уже выписанных чисел. Нетрудно изобрести прием и для отсчитывания и вычеркивания каждого р-го числа начиная с (kр+1)-го для k=1, 2, ..., но мы на этом останавливаться не будем.

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

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

Теперь нетрудно составить алгоритм разложения про¬извольного числа на простые сомножители. Предварительно рассмотрим один вид действия, с ко¬торым мы уже встречались раньше, но не обратили на него особого внимания. Это — проверка условия. Пункты 1 и 2 алгоритма Евклида и п. 3 алгоритма Эратосфена требуют проверки условия. У нас эти пункты сформулиро¬ваны так: «если... (условие)... то... иначе...» То есть они требуют проверки условия, и если оно выполнено, то предписывают один образ действий, а если не выполнено, то другой.

В результате проверки условия мы получаем либо ответ «да», либо ответ «нет». Само условие имеет вид утверждения, например: р2>n. В математической логике условия называются предикатами. В общем случае условие в своем тексте содержит одно или несколько «групповых» имен каких-либо предметов и утверждает наличие некоторого свойства у предметов или отношения между ними. Так, условие «р2 > n» содержит два групповых имени: Р (или «простое число») и n (иkи «заданное положительное целое число»).

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

Представьте себе, например, условие «р — простое число». Легко ли проверить это условие для числа 1037, т. е. увидеть, является ли оно простым? Тем не менее проверить это можно с помощью алгоритма Эратосфена. В математической логике, изучающей предикаты, говорят, что предикаты ставят в соответствие набору предметов, для которых проверяется условие, определенное логическое значение. Что же представляет собой это логическое значение? Одним таким логическим значением является истина, а другим — ложь. По сами эти слова не являются логическими значениями, а лишь обозначают их собой, подобно тому, как числом два является не само слово «два». Частным случаем предиката является условие, в котором «групповые» имена вырождены в «индивидуальные» имена. Это имеет место, например, для условия 22 > 5. Такое условие тоже может быть проверено, но только для двух конкретных предметов (для чисел 2 и 5). При его проверке мы получили бы логическое значение ложь. Предикаты, содержащие в своем тексте не групповые, а только индивидуальные имена, называются высказываниями. Каждое высказывание имеет неизменное логическое значение (в нашем примере — ложь), тогда как в случае невырожденных групповых имен для их конкретных значений (т. е. при их замене индивидуальными именами) могут получаться различные логические значения: иногда истина, иногда ложь.

При составлении алгоритмов нужно следить за тем чтобы способ проверки включаемых в них условий был известен (в виде соответствующего алгоритма).

Теперь приступим к составлению алгоритма разложения положительного целого числа N на простые множители.

1. Составить в порядке возрастания последовательность простых чисел, каждое из которых не больше N. Именем р называть простое число 2. Считать, что произведение П состоит из единственного множителя, равного единице. Перейти к п. 2.
2. Если N является простым числом (в этом случае оно стоит среди полученных простых чисел на последнем месте), то перейти к п. 7, иначе перейти к п. 3.
3. Если общий наибольший делитель чисел N и р равен 1, перейти к п. 4, иначе перейти к п. 6.
4. Найти следующее за р по величине простое число. Впредь его называть именем р. Перейти к п. 5.
5. Если р2 > N, то перейти к п. 7, иначе перейти к п. 3.
6. Разделить N на р. Частное считать новым значени¬ем N. К произведению П приписать точку (знак умножения) и за ней число, являющееся значением р. В дальнейшем именем П называть новое произведение. Вернуться к п. 3.
7. Приписать к произведению П точку (знак умножения) и за ней число N. В дальнейшем буквой П будем обозначать новое произведение. Перейти к п. 8.
8. В произведении П произведения одинаковых простых чисел заменить их степенями, стоящую на первом месте единицу отбросить. Ответ получен. Процесс окончен.

Читатель может сам выполнить этот алгоритм, применительно к числу N=504 и при этом получить N=23*32*7. Корректность алгоритма разложения положительного целого на простые сомножители доказать очень просто. Предоставим это читателю. Очень просто теперь составить алгоритм получения наименьшего кратного нескольких чисел. Он будет состоять в следующем.

1. Заданные числа N1, N2,…,Nn разложить на простые cомножители и получить произведения их степеней П1, П2,… Пn. Перейти к п. 2.
2. Составить строку К, выписывая в порядке возрастания простые числа, присутствующие хотя бы в одном из разложений, и разделяя их знаками умножения. Перейти к п. 3.
3. Каждое из простых чисел, входящих в К, возвести в степень, показатель которой равен наибольшему показателю степени того же простого числа в разложениях П1, П2,… Пn. Полученный результат впредь именовать К. Перейти к п. 4.
4. В К произвести все возведения в степень и все умножения. Полученный результат является ответом. Конец.

Корректность этого алгоритма вытекает из того, что:
а) для любого Пi, (1 ? i ? n) путем несложных преобразований и перегруппировки в составе К можно выделить группу сомножителей, совпадающих с Пi, откуда следует, что полученный результат кратен числу Ni;
б) уменьшить полученный результат нельзя, так как уменьшение показателя степени хотя бы одного сомножителя в К привело бы к тому, что результат перестал бы быть кратным хотя бы одному из Пi.