Изменения
→Перебор делителей
{{Определение | 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>O\left(n\dfrac{x}{y} < 1 \right)</tex>, позволяют нам ограничить пространство поиска делителей числа <tex>number</tex> интервалом <font color=whitetex>O(n)[2;number]</fonttex> ===.
==== Основная идея ====
==== Псевдокод нахождения простых множителей ====
<font color=green>// сюда складываем множители</font>
result = '''vector<int>'''
<font color=green>// число, у которого осталось найти множители; </font>
curNum = number
<font color=green>// число, на которое пытаемся делить</font>
probe = 2
'''while''' curNum <tex>\ne</tex> 1
'''if''' curNum '''mod''' probe <tex>\ne 0\, </tex>0
<font color=green>// проверены все множители из [2; probe]</font>
probe++
result += [probe]
'''return''' result
==== Псевдокод нахождения делителей ====
<font color=green>// массив полученных делителей</font>
result = '''vector<int>'''
result += [probe]
'''return''' result
==== Основная идея ====
Из определения: <tex>\sqrt{n} * \cdot \sqrt{n} = n</tex>. Логично, что:
{|
|-align="center"
|rowspan="2"| <tex>\bigg\{</tex>
|<tex>x * \cdot y = \mathtt{number}</tex>|rowspan="2"| <tex>\Longrightarrow x > \sqrt{\mathtt{number}}</tex>
|-align="center"
|<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>, задача может считаться решенной.
==== Псевдокод ====
result = '''vector<int>'''
'''for''' probe = 2 '''to''' <tex>\sqrt{\mathtt{number}}</tex> <font color=green>// <--- обновляем верхнюю границу перебора</font>
'''if''' number '''mod''' probe = 0
result += [probe]
result += [<tex>\mathtt{number}</tex> / probe] <font color=green>// <--- записываем сопряженный делитель</font>
'''return''' result
== Предподсчет ==
{{main|Решето Эратосфена}}
=== Основная идея ===
Решето Эратосфена (англ. ''Sieve of Eratosthenes'') позволяет не только находить простые числа, но и находить простые множители числа. Для этого необходимо хранить (помимо самого "решета") массив простых чисел, на которое каждое число делится (достаточно одного простого делителя).
=== Псевдокод ===
<font color=green>// возвращает только дополнительный массив</font>
'''function''' <tex>\mathrm{sieveOfEratosthenes}</tex>(n: '''int'''): '''int'''[n+ 1]''' result = [n + 1] result[n]= n
<font color=green>// выбираем следующий простой делитель</font>
'''for''' i = 2 '''to''' <tex>\sqrt{\mathtt{n}}</tex> '''if''' result[i] <tex>\ne</tex> ''null''= 0 <font color=green>// {{Acronym|записываем |в этой реализации и переписываем тоже}}делитель в элементы массива,
// соответствующие числа которых делятся нацело</font>
shuttle = <tex>\mathtt{i}^2</tex>
'''while''' shuttle <tex>\leqslant</tex> n
result[shuttle] = i
'''return''' result
'''function''' <tex>\mathrm{getMultipliers}</tex>(number: '''int'''): '''vector<int>'''
result = '''vector<int>'''
<font color=green>// получаем дополненное решето Эратосфена</font>
sieve = <tex>\mathrm{sieveOfEratosthenes}</tex>(number)
<font color=green>// следующее временное значение получаем
// делением предыдущего на простой делитель из решета</font>
curNum = number
'''while''' sieve[curNum] <tex>\ne</tex> ''null''1 result += sieve[sieveNumcurNum]
curNum /= sieve[curNum]
'''return''' result
== См. также ==
*[[Решето Эратосфена]]
*[[Основная теорема арифметики]]
*[[Дискретная математика, алгоритмы и структуры данных#Комбинаторика | Комбинаторика]]
== Источники информации ==
* Маврин П.Ю. - — Лекция по алгоритмам над простыми числами (2016)
* [https://ru.wikipedia.org/wiki/Простое_число https://ru.wikipedia.org/wiki/Простое_число]
[[Категория: Алгоритмы алгебры и теории чисел]]
[[Категория: Теория чисел]]