Разложение на простые множители

Всякое составное число можно единственным способом представить в виде произведения простых множителей. Например,

36=2*2*3*3;
45=3*3*5;
150=2*3*5*5.

Для небольших чисел разложение легко делается по догадке. Для больших чисел можно Пользоваться таким приемом.

Пример 1.
Пусть дано число 1421.
Берем подряд простые числа таблицы и останавливаемся на том, которое является делителем данного числа.
На основании признаков делимости видим, что числа 2, 3, 5 не могут быть делителями числа 1421;
попытавшись разделить на 7, видим, что 1421 делится на 7 и дает в частном 203.
Слева от черты записываем число 1421; справа против него - делитель; под числом - частное 203.
Запись: Таким же образом испытываем число 203.
Чисел 2,3,5, оказавшихся негодными при первой пробе, мы не трогаем и начинаем испытание с числа 7.
Оказывается, что 7 есть делитель числа 203.
Записываем его справа от черты против 203.
Снизу под 203 пишем частное 29.
Число 29 - простое, поэтому разложение закончено.

Результат его:1421=7*7*29.

Этот общий способ можно в ряде случаев упрощать.

Пример 2.
Разложим на простые множители число 1237600.
Заметив, что 1237600=12376*100, разложим по отдельности два сомножителя.
Второй разлагается сразу: 100=10*10=2*5*2*5.
Первый разлагаем следующим образом.
Берем первое простое число 2; что оно есть делитель числа 12 376, видно по признаку делимости.
Найдя частное 6188, снова берем число 2.
Второе частное 3094 также четно; делим его опять на 2 (можно было бы и сразу разделить 12 376 на 8, применив предварительно признак делимости на 8).
Результат 1547 уже не делится на 2.
Признаки делимости покажут, что оно не делится ни на 3, ни на 5.
Пробуем делить 1547 на 7; получаем частное 221.
Пробуем еще раз разделить на 7. Не делится.
Тогда испытываем следующие простые числа.
На 11 число 221 не делится, но на 13 делится, в частном-простое число 17.

Результат: 1237600=2*2*2*2*2*5*5*7*13*17.