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

Эта статья находится в разработке!

Проверка числа на простоту за [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].