Изменения
Нет описания правки
== Перебор делителей ==
=== Наивная реализация <tex>O(n)</tex><font color=white>O(n)</font> ===
==== Основная идея ====
[[Основная теорема арифметики#Основная теорема арифметики#Собственно теорема | Основная теорема арифметики]], в купе с утверждением, что <tex>\forall x, y \in \mathbb{N}~~x<y \Longrightarrow</tex> {{Acronym|<tex>\left( \dfrac{x}{y} < 1 \right)</tex>|т.е. y не делит x нацело}}, позволяют нам ограничить пространство поиска делителей числа <tex>\mathtt{number}</tex> интервалом <tex>[2; \mathtt{number}]</tex>.
'''return''' result
</code>
=== Улучшенная реализация <tex>O(\sqrt{n})</tex><font color=white>O(√n)</font> ===
==== Основная идея ====
Из определения: <tex>\sqrt{n} * \sqrt{n} = n</tex>. Логично, что:
