Получить каноническое разложение числа на простые сомножители

Формулировка. Дано натуральное число n (n > 1). Получить его каноническое разложение на простые сомножители, то есть представить в виде произведения простых сомножителей. При этом в разложении допустимо указывать множитель 1. Например, 264 = 2 * 2 * 2 * 3 * 11 (программе допустимо выдать ответ 264 = 1 * 2 * 2 * 2 * 3 * 11).

Решение. Данная задача имеет достаточно красивое решение.

Из основной теоремы арифметики известно, что для любого натурального числа больше 1 существует его каноническое разложение на простые сомножители, причем это разложение единственно с точностью до порядка следования множителей. То есть, например, 12 = 2 * 2 * 2 и 12 = 3 * 2 * 2 – это одинаковые разложения.

Рассмотрим каноническую форму любого числа на конкретном примере. Например, 264 = 2 * 2 * 2 * 3 * 11. Каким образом можно выявить эту структуру? Чтобы ответить на этот вопрос, вспомним изложенные в любом школьном курсе алгебры правила деления одночленов, представив, что числа в каноническом разложении являются переменными. Как известно, если разделить выражение на переменную в некоторой степени, содержащуюся в этом выражении в той же степени, оно вычеркивается в ее записи.

То есть, если мы разделим 264 на 2, то в его каноническом разложении уйдет одна двойка. Затем мы можем проверить, делится ли снова получившееся частное на 2. Ответ будет положительным, но третий раз деление даст остаток. Тогда нужно брать для рассмотрения следующее натуральное число 3 – на него частное разделится один раз. В итоге, проходя числовую прямую в положительном направлении, мы дойдем до числа 11, и после деления на 11 n станет равно 1, что будет говорить о необходимости закончить процедуру.

Почему при таком «вычеркивании» найденных сомножителей мы не получим делимостей на составные числа? На самом деле, здесь все просто – любое составное число является произведением простых сомножителей, меньших его. В итоге получается, что мы вычеркнем из n все сомножители любого составного числа, пока дойдем до него самого в цепочке делений. Например, при таком переборе n никогда не разделится на 4, так как «по пути» к этому числу мы вычеркнем из nвсе сомножители-двойки.

Алгоритм на естественном языке:

1)      Ввод n;

2)      Присвоение переменной p числа 2;

3)      Вывод числа n, знака равенства и единицы для оформления разложения;

4)      Запуск цикла с предусловием n < > 1. В цикле:

  1. Если m mod p = 0, то вывести на экран знак умножения и переменную p, затем разделить n на p, иначе увеличить значение i на 1;

Код:

  1. program PrimeFactors;
  2. var
  3. n, p: word;
  4. begin
  5. p := 2;
  6. readln(n);
  7. write(n, ‘ = 1’);
  8. while n <> 1 do begin
  9. if (n mod p) = 0 then begin
  10. write(‘ * ‘, p);
  11. n := n div p
  12. end
  13. else begin
  14. inc(p)
  15. end
  16. end
  17. end.