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

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

ПОДСЧЁТ КОЛИЧЕСТВА ДЕЛИТЕЛЕЙ

Построение алгоритма подсчёта количества делителей заданного натурального числа Q > 1 проведём методом постепенного его улучшения в сторону повышения быстродействия. При этом случай числа Q = 1, имеющего, очевидно, единственного делителя, равного единице, исключаем как тривиальный.

В простейшем случае задачу подсчёта количества делителей k достаточно легко решить на основе команды повторения с параметром:

k := 0

для D от 1 до Q

выполнять если Q mod D = 0 то k := k + 1

Тут k – счётчик количества делителей, обнуляемый перед циклом. Параметр цикла D является носителем значений потенциальных делителей числа Q (естественно, в пределах от 1 до Q). Если очередное значение D является делителем, то это можно обнаружить, вычислив остаток от деления Q на D. Нулевое значение остатка свидетельствует о том, что очередное значение D – делитель, и поэтому счётчик k должен быть увеличен на 1.

Улучшим этот алгоритм. Напомним, что минимум двух делителей имеет любое число Q > 1. Это единица и само Q. Раз это свойство касается всх чисел, то счётчик числа делителей можно сразу положить равным 2. Проверку же наличия других делителей будем проводить на промежутке от 2 до Q – 1.

k := 2

для D от 2 до Q – 1

выполнять если Q mod D = 0 то k := k + 1

Нам удалось чуть-чуть ускорить работу алгоритма благодаря тому, что мы отдельно учли существование двух делителей, равного 1 и равного самому числу Q. Цикл теперь выполняется не Q раз, а “всего” Q – 2 раза. Интересно, что в данном варианте при Q = 2 цикл не выполняется вообще (для D от 2 до 1). При этом результат k = 2, что, конечно же, правильно.

Продолжим процесс усовершенствования. 

Сначала вспомним одну простую вещь, состоящую в том, что “делители всегда парами ходят”. Действительно, если число Q имеет делителем число D, то вполне естестественно, что в результате деления Q на D получим ещё одного делителя. Например, для числа Q = 42 известен делитель D = 3. Разделив 42 на 3, получим для числа Q = 42 делителя, равного 14.

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

Например, для числа 42 наибольший возможный делитель равен 42 div 2 = 21, для числа 100 наибольший возможный делитель равен 100 div 2 = 50, для числа 15 наибольший возможный делитель равен 5, что не превышает числа 15 div 2 = 7, для числа 33 наибольший возможный делитель равен 11, что не превышает числа 33 div 2 = 16 и т. д.

Обратите внимание, что наибольший возможный делитель равен половине числа Q только в случае чётного Q. При нечётном Q наибольший возможный делитель половины числа Q не достигает.

Всё это даёт нам возможность вдвое ускорить работу алгоритма подсчёта количества делителей.

k := 2

для D от 2 до Q div 2

выполнять если Q mod D = 0 то k := k + 1

Обратим внимание, что в данном варианте цикл не выполняется вообще не только при Q = 2, но и при Q = 3 (для D от 2 до 1). При этом результат k = 2 остаётся правильным.

Продолжаем процесс усовершенствования. 

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

Рассмотрим, например, делителей числа Q = 144. Это число имеет 15 делителей. Исключим из них 1 и 144, а оставшиеся распределим парами так, чтобы в каждой паре произведение делителей равнялось бы 144. Для этого нам придётся делитель 12 записать дважды. Получаем такую таблицу делителей:

Для числа Q = 225, имеющего 9 делителей (включая 1 и 225), аналогичная таблица выглядит следующим образом:

В этой таблице дважды записан делитель 15.

Теперь запишем таблицу делителей для числа Q = 132:

Число Q = 132 имеет 12 делителей (вместе с 1 и 132). При этом ни одного делителя не пришлось вносить в таблицу дважды.

Теперь обратим внимание, что Sqrt ( 144 ) = 12, Sqrt ( 225 ) = 15, а корень квадратный из 132 удовлетворяет условиям 11 < Sqrt ( 132 ) < 12.

На основании этих примеров можно вывести достаточно простое правило для подсчёта общего количества делителей данного числа Q путём просмотра и проверки минимального количества потенциальных делителей:

1) первоначальное количество делителей равно 2;

2) потенциальные делители просматриваем в промежутке от 2 до Sqrt ( Q ) включительно;

3) при нахождении очередного делителя общее их количество увеличиваем на 2;

4) если Q представляет собой точный квадрат, то общее количество делителей следует уменьшить на единицу.

k := 2

для D от 2 до Sqrt(Q)

выполнять если Q mod D = 0 то k := k + 2

если Точный_квадрат (Q) то k := k – 1

Примечание. Здесь использовано обращение к алгоритму Точный_квадрат ( X: нат ): лог  (см. материалы занятия 17).

В данном варианте алгоритма цикл, как и прежде, не выполняется вообще как при Q = 2, так и при Q = 3 (потому, что при этом Sqrt ( Q ) < 2). Результат k = 2 продолжает оставаться правильным.

Таким образом, основным результатом проведённых исследований является то, что нам удалось выяснить, какой минимальный числовой промежуток должен быть просмотрен для правильного определения количества делителей данного числа Q. В этот промежуток входят все целые числа от 2 до Sqrt ( Q ). Например, число 101 имеет только два делителя (1 и 101). Чтобы это выяснить, достаточно проверить возможные делители от 2 до 10 включительно.

Уважаемые подписчики! При необходимости задать вопрос, проконсультироваться, уточнить или обсудить что-либо обращайтесь через Гостевую книгу моего персонального сайта http://a-morgun.narod.ru. При этом настоятельно рекомендую пользоваться браузером Internet Explorer.

С уважением, Александр.