344
правки
Изменения
→Основная идея
[[Основная теорема арифметики#Основная теорема арифметики#Собственно теорема | Основная теорема арифметики]], в купе с утверждением, что <tex>y</tex> не делит <tex>x</tex> нацело: <tex>\forall x, y \in \mathbb{N}~~x<y \Longrightarrow</tex> <tex>\left( \dfrac{x}{y} < 1 \right)</tex>, позволяют нам ограничить пространство поиска делителей числа <tex>number</tex> интервалом [2; <tex>number</tex>].
==== Основная идея ====
Заметим, что если <tex>number</tex> = <tex>\prod p_i = p_1 \cdot p_2 \cdot \ldots \cdot p_{j-1} \cdot p_j \cdot p_{j+1} \cdot \ldots \cdot p_n</tex>, то <tex>\left(\dfrac{number}{p_i}\right) = \prod\limits_{i \ne j} p_i = p_1 \cdot p_2 \cdot \ldots \cdot p_{j-1} \cdot p_{j+1} \cdot \ldots \cdot p_n</tex>. Таким образом, мы можем делить <tex>number</tex> на его {{Acronym|делители|(множители}} ) последовательно и в любом порядке. Тогда будем хранить <tex>curNum \colon curNum \cdot \prod result_i = number</tex> — произведение оставшихся множителей.
==== Псевдокод нахождения простых множителей ====
Алгоритм работает за <tex>O(k)</tex>, где k — количество простых множителей.
