153
правки
Изменения
→Разложение на множители за O(\sqrt{n})
==Разложение на множители за <tex>O(\sqrt{n})</tex>==
Для поиска разложения числа на множители воспользуемся так же простым перебором чисел от <tex>1</tex> до <tex>\sqrt{n}</tex>. С помощью алгоритма проверки простоты найдём первый делитель числа <tex>n</tex> - <tex>m</tex>. Далее <tex>n</tex> сокращается в <tex>m</tex> раз и процедура повторяется. По достижении квадратного корня из <tex>n</tex> и невозможности сократить <tex>n</tex> ни на одно из меньших чисел, <tex>n</tex> объявляется неразложимым.
