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

Материал из ALL
Перейти к: навигация, поиск

Разложение на множители — это нахождение множителей и их степеней в произведении, дающем исходное натуральное число.

Обозначения

n – натуральное число;

k – количество простых чисел для n;

m – количество множителей для n;

pii-ое простое число;

jii-ый множитель;

si – степень i-ого множителя.

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

Входные данные: n; k; {p1,p2,...,pk}.

РНМ01.JPG

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

Алгоритм работает при наличии во входных данных необходимых множителей.

Формула разложения на множители

РНМ02.JPG

Алгоритм можно использовать для разложения на заданные множители при отсутствии во входных данных некоторых необходимых множителей. Для этого необходимо во входных данных указывать только заданные множители, а в выходные данные необходимо добавить величину d, где d – дополнительный множитель для n, после учёта заданных множителей.

Формула разложения на заданные множители

РНМ03.JPG

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

Шаблон:Список ААлг

Ссылки