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

Факторизация числа

❓Инструкция

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

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

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

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

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

! Число на входе должно быть натуральным.
! Максимальная длина введенного числа в символах — 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 2
756 2
378 2
189 3
63 3
21 3
7 7
1  

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

ℹ Заметили неточность в работе калькулятора? Убедительная просьба сообщить об этом в комментариях или через форму обратной связи. Заранее Вас благодарим.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *