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


Условия в программах с циклами - часть 2


выполнить проверку условия цикла (i <= n), а затем снова проверить деление n на уже новое значение i.

Обратите внимание,  что при таком алгоритме в качестве делителей уже не попадут составные числа. Объясните почему?

Программа

Program

Problem3; { Разлож. числа на прост. множит.. 1- й спос. }

    uses WinCrt;

    var

       n, i : integer;

    begin

       write('Введите натуральное число '); readln(n);

       write('Простые делители числа ', n, ' следующие; ');

       i := 2;

       while i <= n do

           if n mod i =0 then

                                    begin

                                       write(i, ' ');

                                       n := n div i

                                    end

                                 else i := i + 1

    end.

Конечно, эта программа далека от совершенства и не может иметь претензии на оригинальность.

Она заставляет компьютер выполнять много лишних проверок на деление.

Вот более совершенный алгоритм.

Он основывается на следующих соображениях.

Вначале находим все делители, равные 2. Для этого последовательно делим число 360 на 2:

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

Делим на 3: 45:3 = 15, 15:3 = 5.

Делим на 5: 5:5 = 1.

Делим на 7, не делится, пробуем делить на следующее нечетное число.

Делим на 9, не делится, переходим к следующему нечетному числу.

Делим на 11, не делится, и так далее.

До тех пор будем пробовать деление на нечетные числа, пока они будут меньше или равны получаемому частному от деления числа на соответствующий делитель.

На основании этих соображений составляем программу.

Program Problem3a;

    uses WinCrt;

    var

       i, n : integer;

    begin

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

    writeln('Простые делители целого числа ', n);

{----------------------------------------------------------------------------------------}




Начало  Назад  Вперед