Калькулятор прайм-факторизации

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

Рекомендации по использованию

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

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

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

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

• Вводимые значения должны быть целыми числами; десятичные и дробные числа не принимаются.
• В качестве входных данных могут использоваться только положительные целые числа больше 1.
• Длина числа не может превышать 13 цифр (без запятых для разделения тысяч), т.е. значение вводимого числа должно быть меньше 10.000.000.000.000.000 или 10000000000000. Таким образом, максимальное вводимое значение составляет 9.999.999.999.999.999 или 9999999999999.

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

Простое число - это целое число больше 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. В итоге, все факторы числа 6 - 1, 2, 3 и 6.

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

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

Например, все факторы числа 12 следующие: 1, 2, 3, 4, 6, 12. Эти факторы записываются в виде списка.

А прайм-факторизация числа 12 будет выглядеть следующим образом: 12 = 2 × 2 × 3. То есть при прайм-факторизации мы получим результаты только в виде простых чисел.

Алгоритм прайм-факторизации

Пробное деление

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

36 ÷ 2 = 18

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

18 ÷ 2 = 9

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

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

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

36 = 2 × 2 × 3 × 3

Это общий способ записи простой факторизации числа. Его также можно записать с помощью экспоненты, например:

36 = 2² × 3²

Дерево простых факторов

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

Пробное деление (любые факторы)

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

Фундаментальная теорема арифметики

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

Применение в реальной жизни

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

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

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

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

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