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

Этот онлайн-калькулятор факторизации находит все простые множители введенного числа. Инструмент показывает результаты в стандартном математическом виде, в степенной форме и в формате CSV. Кроме того, наш калькулятор разложения на множители позволяет сгенерировать дерево факторизации, а также найти абсолютно все (а не только простые) делители заданного числа.

Как пользоваться калькулятором

Чтобы разложить число на простые множители, просто введите нужное значение и нажмите «Вычислить». Калькулятор выведет простые множители числа в стандартном виде, в виде степеней и списком в формате CSV.

Вы также можете построить дерево факторизации и найти все делители заданного числа. Для этого просто поставьте галочки в соответствующих чекбоксах перед началом расчета.

Чтобы удалить введенные данные, нажмите кнопку «Очистить».

Ограничения на ввод данных

• Вводимые значения должны быть целыми числами: десятичные дроби и дробные числа не принимаются.
• Поддерживаются только положительные целые числа больше 1.
• Длина числа не должна превышать 13 цифр (без разделителей разрядов). То есть вводимое значение должно быть меньше 10 000 000 000 000. Таким образом, максимально допустимое число для расчета составляет 9 999 999 999 999.

Простые и составные числа

Простое число — это целое положительное число больше 1, которое делится без остатка только на 1 и на само себя. Другими словами, его нельзя получить путем умножения других целых чисел. Первые простые числа: 2, 3, 5, 7, 11, 13, 17, ... (Обратите внимание, что 2 — единственное четное простое число, все остальные являются нечетными).

Если обозначить n-е простое число в этом ряду как Prime[n], то Prime[1] = 2, Prime[2] = 3, Prime[3] = 5 и так далее. Наш онлайн-калькулятор показывает индекс n для каждого найденного простого числа вплоть до n = 5000.

Составное число — это целое число больше 1, которое имеет более двух делителей, то есть его можно представить в виде произведения других целых чисел. Например, 6 — составное число, так как 6 = 3 × 2. Число 12 также является составным, поскольку 12 = 6 × 2 = 3 × 2 × 2.

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

Числа, при перемножении которых получается другое целое число, называются множителями (или делителями). Как показано в примере выше, 3 и 2 являются множителями числа 6. Поскольку 6 также можно получить умножением 1 на 6 (6 = 1 × 6), числа 1 и 6 тоже считаются делителями шестерки. В итоге, все делители числа 6 — это 1, 2, 3 и 6.

Единственными делителями любого простого числа являются единица и само это число. Например, делители числа 17 — это 1 и 17.

Разложение на простые множители (факторизация) — это процесс нахождения всех простых чисел, произведение которых дает исходное число. Важно понимать, что разложение числа на простые множители отличается от поиска всех его делителей.

Например, полный список делителей числа 12 выглядит так: 1, 2, 3, 4, 6, 12.

А разложение числа 12 на простые множители записывается иначе: 12 = 2 × 2 × 3. При факторизации в результате присутствуют исключительно простые числа.

Алгоритмы разложения на простые множители

Метод пробного деления

Давайте рассмотрим наиболее интуитивный алгоритм факторизации — метод пробного деления. Разберем его на примере поиска простых множителей числа 36. Поскольку простые числа нам известны, мы можем последовательно проверять, делится ли наше число на какое-либо из них без остатка. Удобнее всего начать с наименьшего простого числа — двойки:

36 ÷ 2 = 18

Результат деления — целое число. Значит, 2 — это один из простых множителей числа 36. Но 18 еще не является простым числом, поэтому мы продолжаем процесс и проверяем, делится ли 18 на 2:

18 ÷ 2 = 9

9 — целое число, следовательно, 18 делится на 2.

Попробуем разделить полученный результат еще раз: 9 ÷ 2 = 4,5. Это уже не целое число, значит, 9 не делится на 2 без остатка.

Переходим к следующему простому числу — тройке: 9 ÷ 3 = 3. Результат снова целый, отлично! Более того, полученная в ответе тройка сама по себе является простым числом. Это значит, что мы достигли финального этапа вычислений. Осталось лишь записать окончательный ответ:

36 = 2 × 2 × 3 × 3

Это стандартная форма записи разложения числа на простые множители. Результат также можно выразить в степенной форме:

36 = 2² × 3²

Дерево простых множителей

Процесс поиска простых множителей можно наглядно визуализировать с помощью так называемого «дерева факторизации». Для числа 36 дерево простых множителей будет выглядеть следующим образом:

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

Иногда процесс факторизации можно значительно упростить. Для этого исходное число сначала представляют в виде произведения двух составных множителей, а затем раскладывают на простые числа каждый из них. Например, давайте найдем простые множители числа 48. Из таблицы умножения мы знаем, что 48 = 6 × 8. Теперь находим простые множители для шестерки (6 = 2 × 3) и для восьмерки (8 = 2 × 2 × 2). Соединив результаты, получаем: 48 = 2 × 2 × 2 × 2 × 3 = 2⁴ × 3¹.

Основная теорема арифметики

Любое натуральное число больше единицы можно представить в виде уникального произведения простых множителей. В математике это утверждение известно как основная теорема арифметики (или теорема о единственности разложения на простые множители).

Практическое применение

Простые числа активно используются в современной криптографии и кибербезопасности для шифрования и расшифровки данных. Мы уже знаем, что любое число можно представить как произведение простых множителей, и эта комбинация всегда уникальна. Именно это математическое свойство делает простые числа идеальным инструментом для защиты цифровой информации.

Дело в том, что поиск простых множителей у сверхбольших чисел остается крайне ресурсоемкой задачей даже для современных мощных компьютеров. По этой причине наш калькулятор имеет ограничение на ввод бесконечно больших значений.

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

Представьте, что вы берете два 10-значных простых числа и перемножаете их. Получается число с еще большим количеством цифр. А теперь представьте, сколько времени займет разложение этого числа методом пробного деления...

Этот процесс требует столь колоссальных вычислительных мощностей, что на данный момент ни один классический компьютер не способен найти исходные множители за разумное время. Благодаря этому ваши переписки и банковские данные остаются в безопасности. Однако ситуация может в корне измениться в будущем по мере развития квантовых вычислений.