Изменения

'''Факторизация'' - ' (англ. ''factorization'') — представление объекта в виде произведения других объектов.

'''Разложение на множители''', или '''Факторизация целых чисел'' - ' (англ. ''integer factorization'') — представление числа в виде [[Основная теорема арифметикиНатуральные числа#Основная теорема арифметики#Собственно теорема | произведения его множителей]].

'''Перебор делителей'' ' (англ. ''Trial division'') — алгоритм для факторизации или тестирования простоты числа путем полного перебора всех возможных потенциальных делителей.

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

[[Основная теорема арифметики#Основная теорема арифметики#Собственно теорема | Основная теорема арифметики]], в купе с утверждениемЗаметим, что если <tex>number</tex> = <tex>\forall x, y prod p_i = p_1 \cdot p_2 \cdot \ldots \cdot p_{j-1} \in cdot p_j \mathbbcdot p_{Nj+1}~~x<y \Longrightarrowcdot \ldots \cdot p_n</tex> {{Acronym|, то <tex>\left( \dfrac{xnumber}{yp_j} < 1 \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>|т.е. y не делит x нацело}}Таким образом, позволяют нам ограничить пространство поиска делителей числа мы можем делить <tex>\mathtt{number}</tex> интервалом на его делители (множители) последовательно и в любом порядке. Тогда будем хранить <tex>[2; curNum \colon curNum = \mathttdfrac{number}]{\prod result_i}</tex>— произведение оставшихся множителей.

Алгоритм Так как простых множителей не может быть больше, чем <tex>n</tex>, а в худшем случае (когда число простое, и на каждое итерации <tex>probe</tex> увеличивается на <tex>1</tex>) он работает за <tex>O(kn)</tex>, где k - количество простых множителейто, следовательно, алгоритм работает за <tex>O(n)</tex>.<code> '''function''' <tex>\mathrm{getMultipliers}</tex>(number: '''int'''): '''vector<int>'''

<font color=green>// число, у которого осталось найти множители; </font>

'''if''' curNum '''mod''' probe <tex>\ne 0\, </tex>0

<code> '''function''' <tex>\mathrm{getDividers}</tex>(number: '''int'''): '''vector<int>'''

</code>=== Улучшенная реализация <tex>O(\sqrt{n})</tex><font color=white>O(√n)</font> ===

Из определения: <tex>\sqrt{n} * \cdot \sqrt{n} = n</tex>. Логично, что:

|<tex>x * \cdot y = \mathtt{number}</tex>|rowspan="2"| <tex>\Longrightarrow x > \sqrt{\mathtt{number}}</tex>

|<tex>y < \sqrt{\mathtt{number}}</tex>

Таким образом, любой делитель <tex>d_0 > \sqrt{\mathtt{number}}</tex> однозначно связан с некоторым <tex>d_1 < \sqrt{\mathtt{number}}</tex>. Если мы найдем все делители до <tex>\sqrt{\mathtt{number}}</tex>, задача может считаться решенной.

<code> '''function''' <tex>\mathrm{getDividers}</tex>(<tex>\mathtt{number}</tex>: '''int'''): '''vector<int>'''

'''for''' probe = 2 '''to''' <tex>\sqrt{\mathtt{number}}</tex> <font color=green>// <--- обновляем верхнюю границу перебора</font>

result += [<tex>\mathtt{number}</tex> / probe] <font color=green>// <--- записываем сопряженный делитель</font>

Вообще говоря=== Проверка числа на простоту ===Алгоритм можно переделать для нахождения простых чисел. Число будет простым, представленный выше алгоритм если у него не окажется множителей (и делителей) кроме <tex>\mathrm{getMultipliers}1</tex> ищет простые множители. Чтобы получить разложения (алгоритмы не проверяют делимость на множители необходимо реализовать [[Генерация комбинаторных объектов в лексикографическом порядке|перебор разбиений]] мультимножества простых множителей на подмножества, тогда, перемножив элементы подмножеств, мы получим множители<tex>1</tex>) и самого числа (улучшенная реализация опускает этот делитель).  

Решето Эратосфена (англ. ''Sieve of Eratosthenes'') позволяет не только находить простые числа, но и находить простые множители числа. Для этого необходимо хранить (помимо самого "решета") массив простых чисел, на которое каждое число делится (достаточно одного простого делителя).

'''function''' <tex>\mathrm{sieveOfEratosthenes}</tex>(n: '''int'''): '''int'''[n+ 1]''' result = [n + 1] result[n]= n

'''for''' i = 2 '''to''' <tex>\sqrt{\mathtt{n}}</tex> '''if''' result[i] <tex>\ne</tex> ''null''= 0 <font color=green>// {{Acronym|записываем |в этой реализации и переписываем тоже}}делитель в элементы массива,

shuttle = <tex>\mathtt{i}^2</tex>

'''function''' <tex>\mathrm{getMultipliers}</tex>(number: '''int'''): '''vector<int>'''

sieve = <tex>\mathrm{sieveOfEratosthenes}</tex>(number)

'''while''' sieve[curNum] <tex>\ne</tex> ''null''1 result += sieve[sieveNumcurNum]

* Маврин П.Ю. - — Лекция по алгоритмам над простыми числами (2016)