Алгоритм разложения чисел на простые множители

Алгоритм А (Разложение на простые множители путем деления). По данному положительному целому числу N этот алгоритм находит простые множители p ₁ ≤ р ₂ ≤ … ≤ p_t числа N. В этом методе используется вспомогательная последовательность пробных делителей

d = d ₀ < d ₁ < d ₂ < d ₃ < …,

которая включает в себя все простые числа < (и, если это удобно, может содержать числа, не являющиеся простыми). Последовательность чисел d_i должна также содержать по крайней мере одно значение, такое, что d_k > .

А1. [Начальная установка.] Присвоить t ← 0, k ← 0, n ← N. (В ходе выполнения алгоритма переменные t, k, n подчинены следующим условиям: " n = N / p ₁... p_t и n не имеет простых множителей, меньших d_k ".)

А2. [ n = 1?] Если n = 1, алгоритм заканчивается.

A3. [Разделить.] Присвоить q ← , r ← n mod d_k. (Здесь q и r - соответственно частное и остаток от деления числа n на d_k.)

А4. [Остаток равен нулю?] Если r ≠ 0, то перейти к шагу А6.

А5. [Множитель найден.] Увеличить t на 1 и присвоить p_t ← d_k, n ← q. Возвратиться к шагу А2.

А6. [Частное мало?] Если q > d_k, увеличить k на 1 и возвратиться к шагу A3.

А7. [ n — простое число.] Увеличить t на 1, присвоить p_t ← n и завершить выполнение алгоритма.

Рис.32. Алгоритм разложения числа на простые множители.