Разложение на множители (факторизация)

Перебор делителей — алгоритм факторизации или тестирования простоты числа путем полного перебора всех возможных потенциальных делителей.

Проверка числа на простоту за [math]O(\sqrt{n})[/math]

Обычно перебор делителей заключается в переборе всех целых (как вариант: простых) чисел от 2 до квадратного корня из факторизуемого числа n и в вычислении остатка от деления n на каждое из этих чисел. Если остаток от деления на некоторое число m равен нулю, то m является делителем n. В этом случае либо n объявляется составным, и алгоритм заканчивает работу.

Таким образом, осуществляя проверку на делимость за [math]O(n)[/math] и перебирая не более [math]\sqrt{n}[/math] чисел, получаем максимальную оценку времени работы алгоритма: [math]O(\sqrt{n})[/math].

Разложение на множители за [math]O(\sqrt{n})[/math]

Для поиска разложения числа на множители воспользуемся так же простым перебором чисел от [math]1[/math] до [math]\sqrt{n}[/math]. С помощью алгоритма проверки простоты найдём первый делитель числа [math]n[/math] - [math]m[/math]. Далее [math]n[/math] сокращается в [math]m[/math] раз и процедура повторяется. По достижении квадратного корня из [math]n[/math] и невозможности сократить [math]n[/math] ни на одно из меньших чисел, [math]n[/math] объявляется неразложимым.