Разложение на множители (факторизация)

2018-03-18T11:36:08Z

91.108.28.61:

{{Определение | definition=
''Факторизация'' - представление объекта в виде произведения других объектов.
}}
{{Определение | definition=
''Разложение на множители'', или ''Факторизация целых чисел'' - представление числа в виде [[Основная теорема арифметики#Основная теорема арифметики#Собственно теорема | произведения его множителей]].
}}

{{Определение | definition=
''Перебор делителей'' — алгоритм факторизации или тестирования простоты числа путем полного перебора всех возможных потенциальных делителей.
}}

== Перебор делителей ==
=== Наивная реализация <tex>O(n)</tex> ===
==== Основная идея ====
[[Основная теорема арифметики#Основная теорема арифметики#Собственно теорема | Основная теорема арифметики]], в купе с утверждением, что <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>.

Заметим, что если <tex>\mathtt{number} = \prod p_i = p_1 * p_2 * \dots * p_{j-1} * p_j * p_{j+1} * \dots * p_n</tex>, то <tex>\left(\dfrac{\mathtt{number}}{p_i}\right) = \prod\limits_{i \ne j} p_i = p_1 * p_2 * \dots * p_{j-1} * p_{j+1} * \dots * p_n</tex>. Таким образом, мы можем делить <tex>\mathtt{number}</tex> на его {{Acronym|делители|множители}} последовательно и в любом порядке. Тогда будем хранить <tex>\mathtt{curNum} \colon \mathtt{curNum} * \prod \mathtt{result_i} =\mathtt{number}</tex> - произведение оставшихся множителей.
==== Псевдокод нахождения простых множителей ====
Алгоритм работает за <tex>O(k)</tex>, где k - количество простых множителей.
<code>
'''function''' <tex>\mathrm{getMultipliers}</tex>(number: '''int'''): '''vector<int>'''
// сюда складываем множители
result = '''vector<int>'''
// число, у которого осталось найти множители; 
curNum = number
// число, на которое пытаемся делить
probe = 2
'''while''' curNum <tex>\ne</tex> 1
'''if''' curNum '''mod''' probe <tex>\ne 0</tex>
// проверены все множители из [2; probe]
probe++
'''else'''
// делим пока делится
curNum /= probe
result += [probe]
'''return''' result
</code>
==== Псевдокод нахождения делителей ====
<code>
'''function''' <tex>\mathrm{getDividers}</tex>(number: '''int'''): '''vector<int>'''
// массив полученных делителей
result = '''vector<int>'''
// перебираем все потенциальные делители
'''for''' probe = 2 '''to''' number
'''if''' number '''mod''' probe = 0
// probe делит number нацело
result += [probe]
'''return''' result
</code>
=== Улучшенная реализация <tex>O(\sqrt{n})</tex> ===
==== Основная идея ====
Из определения: <tex>\sqrt{n} * \sqrt{n} = n</tex>. Логично, что:
{|
|-align="center"
|rowspan="2"| <tex>\bigg\{</tex>
|<tex>x * 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>, задача может считаться решенной.
==== Псевдокод ====
<code>
'''function''' <tex>\mathrm{getDividers}</tex>(<tex>\mathtt{number}</tex>: '''int'''): '''vector<int>'''
result = '''vector<int>'''
'''for''' probe = 2 '''to''' <tex>\sqrt{\mathtt{number}}</tex> // <--- обновляем верхнюю границу перебора
'''if''' number '''mod''' probe = 0
result += [probe]
result += [<tex>\mathtt{number}</tex> / probe] // <--- записываем сопряженный делитель
'''return''' result
</code>
=== Проверка числа на простоту. Множители ===
Алгоритм можно переделать для нахождения простых чисел. Число будет простым, если у него не окажется {{Acronym|множителей|и делителей}} кроме 1 (алгоритмы не проверяют делимость на 1) и самого числа (улучшенная реализация опускает этот делитель). Исключительный случай: <tex>\mathtt{number} = 2</tex>.

Вообще говоря, представленный выше алгоритм <tex>\mathrm{getMultipliers}</tex> ищет простые множители. Чтобы получить разложения на множители необходимо реализовать [[Генерация комбинаторных объектов в лексикографическом порядке|перебор разбиений]] мультимножества простых множителей на подмножества, тогда, перемножив элементы подмножеств, мы получим множители.
== Предподсчет ==
{{main|Решето Эратосфена}}
=== Основная идея ===
Решето Эратосфена позволяет не только находить простые числа, но и находить простые множители числа. Для этого необходимо хранить (помимо самого "решета") массив простых чисел, на которое каждое число делится (достаточно одного простого делителя).
=== Псевдокод ===
<code>
// возвращает только дополнительный массив
'''function''' <tex>\mathrm{sieveOfEratosthenes}</tex>(n: '''int'''): '''int[n]'''
result = [n]
// выбираем следующий простой делитель
'''for''' i = 2 '''to''' <tex>\sqrt{\mathtt{n}}</tex>
'''if''' result[i] <tex>\ne</tex> ''null''
// {{Acronym|записываем |в этой реализации и переписываем тоже}}делитель в элементы массива,
// соответствующие числа которых делятся нацело
shuttle = <tex>\mathtt{i}^2</tex>
'''while''' shuttle <tex>\leqslant</tex> n
result[shuttle] = i
shuttle += i
'''return''' result

'''function''' <tex>\mathrm{getMultipliers}</tex>(number: '''int'''): '''vector<int>'''
result = '''vector<int>'''
// получаем дополненное решето Эратосфена
sieve = <tex>\mathrm{sieveOfEratosthenes}</tex>(number)
// следующее временное значение получаем
// делением предыдущего на простой делитель из решета
curNum = number
'''while''' sieve[curNum] <tex>\ne</tex> ''null''
result += [sieveNum]
curNum /= sieve[curNum]
result += [curNum]
'''return''' result
</code>
== См. также ==
*[[Решето Эратосфена]]
*[[Основная теорема арифметики]]
*[[Дискретная математика, алгоритмы и структуры данных#Комбинаторика | Комбинаторика]]
== Источники информации ==
* Маврин П.Ю. - Лекция по алгоритмам над простыми числами (2016)
* [https://ru.wikipedia.org/wiki/Простое_число https://ru.wikipedia.org/wiki/Простое_число]
[[Категория: Алгоритмы алгебры и теории чисел]]

Викиконспекты - Вклад участника [ru]

Разложение на множители (факторизация)