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

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

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

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

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

Представьте себе, например, условие «р — простое число». Легко ли проверить это условие для числа 1037, т. е. увидеть, является ли оно простым? Тем не менее проверить это можно с помощью алгоритма Эратосфена.

В математической логике, изучающей предикаты, го­ворят, что предикаты ставят в соответствие набору пред­метов, для которых проверяется условие, определенное логическое значение.

Что же представляет собой это логическое значение? Одним таким логическим значением является истина, а другим — ложь. Но сами эти слова не являются логиче­скими значениями, а лишь обозначают их собой, подобно тому, как числом два является не само слово «два».

Частным случаем предиката является условие, в кото­ром групповые имена вырождены в индивидуальные имена. Это имеет место, например, для условия

2²>5.

При его проверке мы получили бы логическое значение ложь.

Предикаты, содержащие в своем тексте не групповые, а только индивидуальные имена, называются высказыва­ниями. Каждое высказывание имеет неизменное логическое значение (в нашем примере — ложь), тогда как в 1учае невырожденных групповых имен для их конкретных значений (т. е. при их замене индивидуальными име­нами) могут получаться различные логические значения: иногда истина, иногда ложь.

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

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

1. Составить в порядке возрастания последовательность всех простых чисел, каждое из которых не больше N. Именем р называть простое число 2. Считать, что произ­ведение П состоит из единственного множителя, равного единице. Перейти к п. 2.

2. Если N является простым числом (в этом случае оно стоит среди полученных простых чисел на последнем ме­сте), то перейти к п. 7, иначе перейти к п. 3.

3. Если наибольший общий делитель чисел N и р ра­вен 1, перейти к п. 4, иначе перейти к п. 6.

4. Найти следующее за р по величине простое число. Впредь его называть именем р. Перейти к п. 5.

5. Если p²>N, то перейти к п. 7, иначе перейти к п. 3.

6. Разделить N на р.Частное считать новым значени­ем N. К произведению П приписать точку (знак умноже­ния) и за ней число, являющееся значением р. В даль­нейшем именем П называть новое произведение. Вернуть­ся к п. 3.

7. Приписать к произведению П точку (знак умноже­ния) и за ней число N. В дальнейшем буквой П будем обозначать новое произведение. Перейти к п. 8.

8. В произведении П произведения одинаковых про­стых чисел заменить их степенями, стоящую на первом месте единицу отбросить. Ответ получен. Процесс окончен.

Читатель может сам выполнить этот алгоритм приме­нительно к числу N=504 и при этом получить N=2³∙3²∙7.

Корректность алгоритма разложения положительного целого на простые сомножители доказать очень просто. Предоставим это читателю.

Очень просто теперь составить алгоритм получения наименьшего кратного нескольких чисел. Он будет со­стоять в следующем.

1. Заданные числа N₁, N₂,…, N_n разложить на про­стые сомножители и получить произведения их степеней П₁, П₂, …, П_n. Перейти к п. 2.

2. Составить строку К, выписывая в порядке возраста­ния простые числа, присутствующие хотя бы в одном из разложений, и разделяя их знаками умножения. Перейти к и. 3.

3. Каждое из простых чисел, входящих в К, возвести в степень, показатель которой равен наибольшему пока­зателю степени того же простого числа в разложениях П₁, П₂, …, П_n. Полученный результат впредь именовать К. Перейти к п. 4.

4. В К произвести все возведения в степень и все ум­ножения. Полученный результат является ответом. Конец.

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