Разложение натурального числа на простые множители
Разложение на множители — это нахождение простых сомножителей и их степеней в произведении, дающем исходное натуральное число. Подобное разложение существует и единственно (с точностью до порядка сомножителей) согласно основной теореме арифметики.
[править] Обозначения
Введём обозначения: pi — 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; {p1, p2, … pk}.
Выходные данные: 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}.
[править] Другие алгоритмы
- наибольший общий делитель;
- наименьшее общее кратное;
- проверка кратности;
- деление по модулю;
- решето Эратосфена;
- разложение числа на множители;
- система счисления;
- метод математической индукции;
- схема примитивной рекурсии;
- виды рекурсии;
- машина Поста;
- машина Тьюринга (вероятностная);
- комбинаторные алгоритмы;
- сортировка;
- алгоритм определения мест.