Расширение алгоритма для нахождения разложения числа на простые множители

Предположим, что в результате применения алгоритма разложения путем деления методом проб к n мы нашли делитель q₁ этого числа. Тогда q₁ – его наименьший простой множитель. Применим тот же алгоритм к числу n / q₁. Предположим, что число n / q₁ составное и q₂ – его наименьший простой делитель. Ясно, что q₂ ≥ q₁. Заметим, однако, что эти делители могут оказаться равными. Такая возможность реализуется, если n делится на q₁². Продолжая в том же духе, мы применяем алгоритм к n / (q₁ q₂) и т.д. В результате мы получаем последовательность простых чисел q₁ ≤ q₂ ≤ q₃ ≤ … ≤ q_s, каждое из которых является делителем числа n. Критерием завершения работы алгоритма является получение делителя q_k равного 1.