Изменения
→Перебор делителей
{{Определение | definition='''Факторизация''' (англ. ''factorization'') — представление объекта в виде произведения других объектов.}}{{Определение | definition='''Разложение на множители''', или '''Факторизация целых чисел''' (англ. ''integer factorization'') — представление числа в виде [[Натуральные числа#Основная теорема арифметики | произведения его множителей]].}}== Перебор делителей=={{Определение | definition='''Перебор делителей''' (англ. ''Trial division'') — алгоритм для факторизации или тестирования простоты числа путем полного перебора всех возможных потенциальных делителей.}}=== Наивная реализация O(n) ===[[Основная теорема арифметики#Основная теорема арифметики#Собственно теорема | Основная теорема арифметики]], вкупе с утверждением, что <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> интервалом <tex>[2;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_j}\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> на его делители (множители) последовательно и в любом порядке. Тогда будем хранить <tex>curNum \colon curNum = \dfrac{number}{\prod result_i}</tex> — произведение оставшихся множителей.
==Проверка числа == Псевдокод нахождения простых множителей ====Так как простых множителей не может быть больше, чем <tex>n</tex>, а в худшем случае (когда число простое, и на простоту каждое итерации <tex>probe</tex> увеличивается на <tex>1</tex>) он работает за <tex>O(n)</tex>, то, следовательно, алгоритм работает за <tex>O(\sqrt{n})</tex>==.
'''function''' getDividers(number: '''int'''): '''vector<int>''' <font color=green>// массив полученных делителей</font> result =Разложение на множители за '''vector<texint>O(\sqrt{n})''' <font color=green>// перебираем все потенциальные делители</texfont> '''for''' probe =2 '''to''' number '''if''' number '''mod''' probe = 0 <font color=green>// probe делит number нацело</font> result +=[probe] '''return''' result