Задача 76218

Темы:    [ Знакомство с циклами ] [ Условный оператор ] [ Задачи с целыми числами ]

Сложность: 1+ Классы:

Условие

Составить программу, печатающую разложение на простые множители заданного натурального числа n > 0 (другими словами, требуется печатать только простые числа и произведение напечатанных чисел должно быть равно n; если n = 1, печатать ничего не надо).

Решение

Вариант 1.

     k := n;
     {инвариант: произведение напечатанных чисел и k равно
      n, напечатаны только простые числа}
     while not (k = 1) do begin
     | l := 2;
     | {инвариант: k не имеет делителей в интервале (1,l)}
     | while k mod l <> 0 do begin
     | | l := l + 1;
     | end;
     | {l - наименьший делитель k, больший 1, следовательно,
     |  простой}
     | writeln (l);
     | k:=k div l;
     end;

Вариант 2.

     k := n; l := 2;
     {произведение  k и напечатанных чисел равно n; напечатанные
      числа просты; k не имеет делителей, меньших l}
     while not (k = 1) do begin
     | if k mod l = 0  then begin
     | | {k делится на l и не имеет делителей,
     | |   меньших l, значит, l просто}
     | | k := k div l;
     | | writeln (l);
     | end else begin
     | | { k не делится на l }
     | | l := l+1;
     | end;
     end;

Источники и прецеденты использования

книга
Автор	А.Шень
Название	Программирование: теоремы и задачи
Издательство	МЦНМО
Издание	второе
Год издания	2004
глава
Номер	1
Название	Переменные, выражения, присваивания
параграф
Номер	1
Название	Задачи без массивов
задача
Номер	1.1.22