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

Умная факторизация чисел с построением интерактивного дерева и канонической записи.

Ввод данных

Введите натуральное число ( > 1 )

Поддерживаются числа до 100 миллионов.

Подсказка: Дерево справа интерактивно. Вы можете перетаскивать его мышью (pan) или изменять масштаб колесиком (zoom).

Что такое простое число?

Это число, которое делится без остатка только на 1 и само на себя.
Примеры: 2, 3, 5, 7, 11, 13...

ДЕРЕВО МНОЖИТЕЛЕЙ

Каноническое разложение:

$$ 360 = 2^3 \times 3^2 \times 5 $$

Прямая запись: 2 × 2 × 2 × 3 × 3 × 5

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

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

Алгоритм

Как построить дерево?

Начните делить число на наименьшее простое число (обычно это 2). Если делится без остатка — запишите 2 как первую ветвь, а результат деления как вторую. Повторяйте процесс для второй ветви, пока на концах не останутся только простые числа.

Запись

Каноническая форма

Для удобства одинаковые простые множители группируют в степени. Например, запись $2 \times 2 \times 3$ математически грамотно сворачивается в каноническую форму: $2^2 \times 3$.

Зачем это нужно на практике?

Сфера применения	Как используется факторизация
Школьная математика	Поиск НОД (наибольшего общего делителя) и НОК (наименьшего общего кратного) для приведения дробей к общему знаменателю.
Криптография (IT)	Основа безопасности алгоритма RSA (защита банков и интернета). Перемножить два гигантских простых числа легко, а вот разложить результат обратно на множители — задача, на которую у суперкомпьютеров уйдут тысячи лет.
Упрощение корней	Разложение помогает извлекать корни: $\sqrt{360} = \sqrt{2^2 \cdot 2 \cdot 3^2 \cdot 5} = 2 \cdot 3 \cdot \sqrt{10} = 6\sqrt{10}$.

Частые вопросы (FAQ)

Является ли 1 (единица) простым числом?

Нет, в современной математике 1 не считается ни простым, ни составным числом. Если бы мы считали 1 простым числом, нарушилась бы Основная теорема арифметики, так как число 6 можно было бы записать бесконечным числом способов: $2 \times 3$, $1 \times 2 \times 3$, $1 \times 1 \times 2 \times 3$ и так далее.

Какое самое большое простое число известно человечеству?

Математики постоянно находят новые простые числа Мерсенна. На текущий момент рекордные числа содержат десятки миллионов знаков! Их поиск осуществляется распределенными сетями компьютеров по всему миру (проект GIMPS).