Разложение натурального числа на простые множители

Лекция 22: Разложение числа на простые множители // НОУ ИНТУИТ [9:48]

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

Обозначения

Введём обозначения: p_i — i-ое простое число;

n — натуральное число, для которого ищется разложение вида [math]n = p_{j_1}^{s_1}\cdot p_{j_2}^{s_2}\cdot\ \cdot p_{j_m}^{s_m}[/math];

m — количество различных простых множителей в числе n;

j_ℓ — номер простого числа в основании ℓ-ого множителя;

s_ℓ — показатель степени ℓ-ого множителя;

k — длина списка простых чисел, поиск которых (в качестве множителя) проводит алгоритм.

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

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

Входные данные: n; k; {p₁, p₂, … p_k}.

Выходные данные: m; {j₁, j₂, … j_m}; {s₁, s₂, … s_m}.

Алгоритм даёт указанное разложение при наличии во входном списке {p_i} всех простых делителей числа n. Если какие-то делители пропущены, то получается разложение вида [math]n = d\cdot p_{j_1}^{s_1}\cdot p_{j_2}^{s_2}\cdot\ \cdot p_{j_m}^{s_m}[/math], где d — натуральное число, не делящееся на простые числа из списка {p_i}.

Другие алгоритмы

• наибольший общий делитель;
• наименьшее общее кратное;
• проверка кратности;
• деление по модулю;
• решето Эратосфена;
• разложение числа на множители;
• система счисления;
• метод математической индукции;
• схема примитивной рекурсии;
• виды рекурсии;
• машина Поста;
• машина Тьюринга (вероятностная);
• комбинаторные алгоритмы;
• сортировка;
• алгоритм определения мест.