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

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

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

[править] Обозначения

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

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; {p1, p2, … pk}.

РНМ01.JPG

Выходные данные: m; {j1, j2, … jm}; {s1, s2, … sm}.

Алгоритм даёт указанное разложение при наличии во входном списке {pi} всех простых делителей числа 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 — натуральное число, не делящееся на простые числа из списка {pi}.

[править] Другие алгоритмы

Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты