ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .