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

program razl; var n,f:integer;

function deco(n,x:integer):integer; {var n,x:integer;}

begin {:=m1;x:=n1;}

if (x=1) then deco:=1

else if n mod x=0 then deco:=deco(n,x-1)+1 else deco:=deco(n,x-1);

end; begin

write('Введите значение n '); readln(n);

f:=deco(n,n);

writeln('количество делителей = ',f); end.

Список задач раздела 14

3.1. Даны две последовательности

x[1]..x[n] и y[1]..y[k] целых чисел. Выяснить, является ли вторая последовательность подпоследовательностью первой, т. е. можно ли из первой вычеркнуть некоторые члены так, чтобы осталась вторая. Число действий порядка n+k.

3.2.Даны две последовательности x[1]..x[n] и

обеих последовательностей. Количество операций порядка n*k.

3.3. Имеется n одинаковых на вид камней, некоторые из которых на самом деле различны по весу. Имеется прибор,

92

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

Предостережение. Если два камня одинаковые, это не гарантирует их принадлежности к большинству.

3.4. Написать рекурсивную программу, которая печатает по одному разу все последовательности длины n, составленные из чисел 1..k (их количество равно k в степени n).

3.5. Написать рекурсивную программу, которая печатала бы все перестановки чисел 1..n по одному разу.

3.6. Перечислить все представления положительного целого числа n в виде суммы последовательности невозрастающих целых положительных слагаемых.

3.7. Перечислить все разбиения целого положительного числа n на целые положительные слагаемые (разбиения, отличающиеся лишь порядком слагаемых, считаются за одно). (Пример: n=4, разбиения 1+1+1+1, 2+1+1, 2+2, 3+1, 4.)

3.8. Имеется n положительных целых чисел x[1]..x[n] и число N. Выяснить, можно ли получить N, складывая некоторые из чисел x[1]..x[n]. Число действий должно быть порядка N*n.

3.9. Найти и вывести на экран число, меньшее 250, которое при делении на 2 дает в остатке 1, при делении на 3 -- 2, при делении на 4 -- 3, при делении на 5 -- 4, при делении на 6 -- 5, а на 7 делится без остатка.

3.10. Найти и распечатать все пары дружественных чисел, меньших 10000. (Дружественные -- два числа, каждое из которых равно сумме правильных делителей другого. Например, 220 и 284.)

93