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

Как разложить число на простые множители. Простой и легкий способ // Мини уроки по математике [6:47]

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

Обозначения

p_i — i-ое простое число;

n — натуральное число, для которого ищется разложение вида $n=p_{j_{1}}^{s_{1}}\cdot p_{j_{2}}^{s_{2}}\cdot \ \cdot p_{j_{m}}^{s_{m}}$;

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

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

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

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

N_k = {1; 2; …; k} — множество натуральных чисел, не превосходящих k.

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

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

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

1. s_i = 0, ∀i ∈ N_k.
2. i = 1; m = 0; d = n.
3. Если d не кратно p_i, то идти к 7.
4. m = m + 1; j_m = i.
5. d = d / p_i; s_m = s_m + 1.
6. Если d кратно p_i, то идти к 5.
7. i = i + 1.
8. Если i ≤ k и d > 1, то идти к 3.

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

Алгоритм даёт указанное разложение при наличии во входном списке {p_i} всех простых делителей числа n. Если какие-то делители пропущены, то получается разложение вида $n=d\cdot p_{j_{1}}^{s_{1}}\cdot p_{j_{2}}^{s_{2}}\cdot \ \cdot p_{j_{m}}^{s_{m}}$, где d — натуральное число, не делящееся на простые числа из списка {p_i}.

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

• Наибольший общий делитель;
• Наименьшее общее кратное;
• Проверка кратности;
• Деление по модулю;
• Получение простых чисел;
• Разложение на множители.