О расчете количества делителей

vmi@1september.ru

Когда человек хочет передвинуть гору,
он начинает с того, что убирает
маленькие камни.

В этой статье мы рассмотрим методику решения в программе такой задачи: “Определить количество делителей натурального числа n”.

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

если mod(a, b) = 0

· то

· число b является делителем числа а

· иначе

· число b не является делителем числа а

все

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

Самый простой способ найти все делители числа n — это проверить по очереди делимость n на каждое из чисел 1, 2, 3, …, n. Соответствующий фрагмент программы имеет вид:

k := 0 |Искомое количество

нц для i от 1 до n

· если mod(n, i) = 0

· · то |i - делитель числа n

· · · k := k + 1

· все

кц

Однако легко убедиться, что в интервале |n/2 + 1; n – 1| делителей числа n нет, т.е. количество проверок можно сократить почти вдвое:

k := 0

нц для i от 1 до div(n, 2)

· если mod(n, i) = 0

· · то

· · · k := k + 1

· все

кц

|Учитываем также число n

k := k + 1

— где div — функция, возвращающая целую часть частного от деления своего первого аргумента на второй.

Можно также учесть тот факт, что у нечетного n четных делителей быть не может:

k := 0

если mod(n, 2) = 0

· то

· · нц для i от 1 до div(n, 2)

· · · если mod(n, i) = 0

· · · · то

· · · · · k := k + 1

· · · все

· · кц

· иначе |n - нечетное число

· · i := 1

· · нц пока i <= div(n, 3)

· · · если mod(n, i) = 0

· · · · то

· · · · · k := k + 1

· · · все

· · · i := i + 2 |Рассматриваем только

· · · |нечетные возможные делители

· · кц

все

|Учитываем также число n

k := k + 1

Количество проверок возможных делителей можно также существенно сократить, если учесть, что у каждого делителя d числа n, не превышающего , есть “симметричный” ему делитель, получающийcя в результате деления n на d. Например, если n = 30, достаточно найти делители 1, 2, 3, 5 (целая часть квадратного корня из 30 равна 5), а все прочие делители получаем следующим образом:

30 div 1 = 30;

30 div 2 = 15;

30 div 3 = 10;

30 div 5 = 6.

Правда, из приведенной методики есть одно исключение — если число n является точным квадратом, то у делителя d, равного , “симметричного” ему делителя нет.

Учтем это в наших программах. При их составлении можно использовать оператор цикла с параметром или оператор цикла с условием. В первом случае фрагмент программы будет иметь вид:

k := 0

нц для i от 1 до int(sqrt(n))

· если mod(n, i) = 0

· · то

· · · |Учитываем i и "симметричный"

· · · |ему делитель

· · · k := k + 2

· все

· i := i + 1

кц

|Проверяем, является ли число n

|точным квадратом

если int(sqrt(n)) = sqrt(n)

· то |Является;

· · |тогда не учитываем 1 делитель

· · k := k - 1

все

При использовании оператора цикла с предусловием фрагмент будет выглядеть так:

k := 0

i := 1

нц пока i * i < n

· если mod(n, i) = 0

· · то

· · · |Учитываем i и "симметричный"

· · · |ему делитель

· · · k := k + 2

· все

· |Рассматриваем следующее число

· i := i + 1

кц

|Проверяем, является ли число n

|точным квадратом.

если i * i = n

· то |Является;

· · |учитываем также квадратный корень из n

· · k := k + 1

все

Несколько комментариев к этому фрагменту. В операторе цикла проверяются числа i, меньшие квадратного корня из n. После окончания работы оператора i может быть равно . В этом случае (число n является точным квадратом) следует учесть и этот делитель.

Можно также отдельно рассматривать вариант, когда n — нечетное число и проверять только нечетные значения i. Именно такой вариант положен в основу вспомогательной функции, рассчитывающей количество делителей числа n:

алг цел Количество_делителей(цел n)

нач цел i, k

· k := 0

· i := 1

· если mod(n, 2) = 0

· · то

· · · нц пока i * i < n

· · · · если mod(n,i) = 0

· · · · · то

· · · · · · k := k + 2

· · · · все

· · · · i := i + 1

· · · кц

· иначе

· · нц пока i * i < n

· · · если mod(n, i) = 0

· · · · то

· · · · · k := k + 2

· · · все

· · · i := i + 2

· · кц

· все

· если i * i = n

· · то

· · · k := k + 1

· все

· знач := k |Значение функции

кон

Задания для самостоятельной работы

1. Найти количество делителей чисел:

а) 81;

б) 600;

в) 1949.

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

3. Определить наименьшее натуральное число, меньшее m, которое имеет максимальное количество различных делителей, при:

а) m = 100;

б) m = 1000;

в) m = 1 000 000.

Ответы (а не программы) присылайте в редакцию. Фамилии всех приславших правильные ответы будут опубликованы.