Разложение числа на множители

 Калькулятор для разложения числа на множители с поддержкой больших чисел. Факторизация натурального числа с решением.

 Как пользоваться:

 В единственное поле требуется ввести натуральное число, которое необходимо разложить на множители.
 Нажать на кнопку «Разложить».
 Получить результат

 Галочка «Подробнее» указывает калькулятору выдать не только ответ, но и этапы работы алгоритма.

Ограничения:

 Число на входе должно быть натуральным.
 Максимальная длина введенного числа в символах — 35.

Так как данный метод факторизации фактически является перебором, то в каких-то определенных случаях (когда очередной делитель — большое число) калькулятор может работать долго, в связи с этим вычисления калькулятором прекращаются, если для очередного простого делителя потребовалось выполнить более 200 000 итераций. Подробнее об алгоритме в разделе теория.

 Рассмотрим еще один алгоритм разложения числа на множители. До этого мы разбирали метод факторизации Ферма. Узнали о слабых и сильных сторонах алгоритма. Текущий алгоритм является интуитивно понятным в отличие от Ферма, так как в какой-то степени является перебором.

 Алгоритм

На входе алгоритма имеем натуральное число n.

1. Методом перебора найдем наименьшее простое число, на которое делится n.
2. Поделим n на найденное простое, для полученного частного аналогично пункту 1 найдем наименьшее простое число, на которое делится частное и поделим.
3. Повторяем действия до тех пор, пока в частном не получим 1.

 В разделе «Примеры» можно на примере разобрать работу алгоритма. Обратим внимание на пункт 1. Простые делители мы находим методом перебора, в связи с этим алгоритм в некоторых случаях может работать долго.

 Рассмотрим в качестве примера натуральное число n = 1512.

1. Нетрудно заметить, что наименьшее простое число, на которое делится 1512 — это 2;
2. Поделим 1512 на 2, получим в частном 756. Теперь n = 756, аналогично находим наименьшее простое число и это снова 2.
3. Делим 756 на 2 получаем в частном 378. Опять же наименьший простой делитель 378 — это 2. Делим и получаем 189.
4. Получили нечетное число, а 2 не делит нечетное число. Наименьшим простым делителем числа 189 является 3, делим и получаем 63.
5. И снова нечетное число и наименьшим простым делителем является 3. Делим и получаем в частном 21.
6. Для 21 наименьшим простым делителем является 3. Делим и получаем 7.
7. Число 7 — является простым, это значит, что наименьший простой делитель 7 — это само число 7.
8. Делим 7 на 7 и получаем в частном 1. В частном получили 1, а значит алгоритм завершает свою работу. Все простые делители всех этапов формируют список простых множителей числа 1512.

 Итого: 1512 = 2 * 2 * 2 * 3 * 3 * 3 * 7

Удобнее всего писать данные в виде таблицы, где левая колонка — частные, а права — наименьшие простые делители.

 Правая колонка — все простые множители числа 1512.