Паскаль. Основы программирования

Для дополнительных занятий


Пример 14. Сколько всех делителей у числа 210? У числа 30030? У целого числа n?

Первая

мысль, которая возникает, - это делить заданное натуральное число на простые числа и подсчитать число простых делителей. Остальные делители получаются всевозможными сочетаниями из простых делителей. Значит, возникает необходимость подсчитать число таких сочетаний, причем сочетания должны быть различными.

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

Пусть p1, ..., pm - различные простые делители числа q. Если

, где
- некоторые натуральные числа, тогда число всех делителей числа q (включая 1 и q) равно числу сочетаний с повторениями (кортежей) показателей степеней a1, a2, ..., am, которое, в свою очередь, равно произведению:

Основываясь на этом предложении составим программу.

Алгоритм

для составления программы может быть таким:

1.

Определяется число простых делителей, равных 2.

2. Число этих делителей увеличивается на 1 и присваивается переменной s.

3. Определяется число нечетных простых делителей.



4. Для каждого простого нечетного делителя устанавливается их число, увеличивается на 1 и умножается на s.

5. Результат - число всех делителей выводится на экран.

Программа

Program Problem14;

     uses WinCrt;

     var

         s, q, m, j, n : integer;

     begin

        write('Введите целое число '); readln(n);

        m := n;

        q := 0;

        s := 0;

        while m mod 2 = 0 do

            begin

               q := q + 1;

               m := m div 2

            end;

        s := q + 1; j := 3; q := 0;

        while j <= m do

            begin

               if m mod j =0 then

                 begin

                    q := q + 1;

                    m := m div j

                 end;

                 s := s*(q + 1);

                if m mod j <> 0 then j := j + 2

            end;

        writeln('К-во всех делителей числа ', n, ' равно ', s)

    end.



Содержание раздела