153
правки
Изменения
→Проверка числа на простоту за O(\sqrt{n})
==Проверка числа на простоту за <tex>O(\sqrt{n})</tex>==
Обычно перебор делителей заключается в переборе всех целых (как вариант: простых) чисел от 2 до квадратного корня из факторизуемого числа ''n'' и в вычислении остатка от деления ''n'' на каждое из этих чисел. Если остаток от деления на некоторое число ''m'' равен нулю, то ''m'' является делителем ''n''. В этом случае либо ''n'' объявляется составным, и алгоритм заканчивает работу.
Таким образом, осуществляя проверку на делимость за <tex>O(n)</tex> и перебирая не более <tex>\sqrt{n}</tex> чисел, получаем максимальную оценку времени работы алгоритма: <tex>O(\sqrt{n})</tex>.
==Разложение на множители за <tex>O(\sqrt{n})</tex>==
