адача 20. Количество делителей. Составить рекурсивную программу-функцию подсчета количества всех положительных делителей натурального числа n.

Решение. Перейдем к более общей задаче. Подсчитаем для натурального числа n количества всех его положительных делителей, меньших или равных заданному натуральному числу x. Пусть dn(n) и dnx(n,x) - соответственно функции для решения исходной и обобщенной задач. Очевидно, что dn(n)=dnx(n,n).

Рекурсивную функцию dnx(n,x), по которой последовательно подвергаются испытанию на делители n все числа от 1 до x включительно, можно определить так:

Трудоемкость вычислений алгоритма решения задачи с использованием функции dn(n) составляет O(n) арифметических операций. Более эффективно эти вычисления можно проводить с помощью пары функций:

Рекурсивная функция dnx2(n,x) аналогична функции dnx(n,x), но подсчитывает удвоенное количество делителей n, не превосходящих x.

Функция dns(n), организуя выбор величины x, обращается к dnx2(n,x) соответственно с x=sq-1 или с x=sq в зависимости от того, является ли n полным квадратом или нет. Этим и обеспечивается правильный учет количества положительных делителей n. Трудоемкость вычислений по dns(n) составляет арифметических операций.

Контрольные примеры:

Заметим, что если n ³ 2 и dns(n)=2, то число n – простое. Однако проверка n на простоту этим способом весьма неэкономна.

адача 21. Делители натурального числа. Составить рекурсивную программу-функцию, возвращающую все положительные делители натурального числа n.

Решение. Самый простой способ найти все положительные делители натурального числа n - это непосредственно проверить по очереди делимость n на каждое из чисел: 2, 3, …, n. Однако при таком подходе будет совершено достаточно много лишней работы. Например, ясно, что в промежутке от floor(n/2)+1 до n-1 делители n отсутствуют.

Нам удобнее перейти к рассмотрению более общей задачи - нахождению делителей числа n в промежутке [d,g], где d и g -  натуральные числа и (1£d£g£n). Пусть div(n,d,g) - программа-функция решения этой вспомогательной задачи. При построении div(n,d,g) параметры d и g будем менять, исходя из того, что для каждого делителя d числа n такого, что d× d£n величина g=n/d также является делителем n и g× g³n. Решение исходной задачи можно будет получать обращением к div(n,1,n) или с помощью функции divi(n), в которой начальные значения d и g определяются автоматически:

Контрольный пример:

Обратите внимание на тот факт, что по функции div(n,d,g) делители n всегда возвращаются в порядке возрастания. Это обеспечивается специальной организацией рекурсивных вычислений. А именно: после нахождения пары делителей d (d× d£n) и g (g× g³n) первый сразу выводится в стек (вектор), а второй заносится туда лишь при отложенных вычислениях после выполнения соответствующего рекурсивного обращения.