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

2021-03-13T23:14:02Z

185.127.225.126: Отмена правки 80691, сделанной 213.87.242.44 (обсуждение)

{{Определение | 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(n)</tex>.

'''function''' getMultipliers(number: '''int'''): '''vector<int>'''
// сюда складываем множители
result = '''vector<int>'''
// число, у которого осталось найти множители
curNum = number
// число, на которое пытаемся делить
probe = 2
'''while''' curNum <tex>\ne</tex> 1
'''if''' curNum '''mod''' probe <tex>\ne\, </tex>0
// проверены все множители из [2; probe]
probe++
'''else'''
// делим пока делится
curNum /= probe
result += [probe]
'''return''' result

==== Псевдокод нахождения делителей ====

'''function''' getDividers(number: '''int'''): '''vector<int>'''
// массив полученных делителей
result = '''vector<int>'''
// перебираем все потенциальные делители
'''for''' probe = 2 '''to''' number
'''if''' number '''mod''' probe = 0
// probe делит number нацело
result += [probe]
'''return''' result

=== Улучшенная реализация <tex>O(\sqrt{n})</tex> ===
==== Основная идея ====
Из определения: <tex>\sqrt{n} \cdot \sqrt{n} = n</tex>. Логично, что:
{|
|-align="center"
|rowspan="2"| <tex>\bigg\{</tex>
|<tex>x \cdot y = number</tex>
|rowspan="2"| <tex>\Longrightarrow x > \sqrt{number}</tex>
|-align="center"
|<tex>y < \sqrt{number}</tex>
|}
Таким образом, любой делитель <tex>d_0 > \sqrt{number}</tex> однозначно связан с некоторым <tex>d_1 < \sqrt{number}</tex>. Если мы найдем все делители до <tex>\sqrt{number}</tex>, задача может считаться решенной.
==== Псевдокод ====

'''function''' getDividers(number: '''int'''): '''vector<int>'''
result = '''vector<int>'''
'''for''' probe = 2 '''to''' <tex>\sqrt{number}</tex> //обновляем верхнюю границу перебора
'''if''' number '''mod''' probe = 0
result += [probe]
result += [number / probe] // записываем сопряженный делитель
'''return''' result

=== Проверка числа на простоту ===
Алгоритм можно переделать для нахождения простых чисел. Число будет простым, если у него не окажется множителей (и делителей) кроме <tex>1</tex> (алгоритмы не проверяют делимость на <tex>1</tex>) и самого числа (улучшенная реализация опускает этот делитель).

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

// возвращает только дополнительный массив
'''function''' sieveOfEratosthenes(n: '''int'''): '''int'''[n + 1]
result = [n + 1]
result[n] = n
// выбираем следующий простой делитель
'''for''' i = 2 '''to''' <tex>\sqrt{n}</tex>
'''if''' result[i] = 0
// записываем делитель в элементы массива,
// соответствующие числа которых делятся нацело
shuttle = <tex>i^2</tex>
'''while''' shuttle <tex>\leqslant</tex> n
result[shuttle] = i
shuttle += i
'''return''' result

'''function''' getMultipliers(number: '''int'''): '''vector<int>'''
result = '''vector<int>'''
// получаем дополненное решето Эратосфена
sieve = sieveOfEratosthenes(number)
// следующее временное значение получаем
// делением предыдущего на простой делитель из решета
curNum = number
'''while''' curNum <tex>\ne</tex> 1
result += sieve[curNum]
curNum /= sieve[curNum]
'''return''' result

== См. также ==
*[[Решето Эратосфена]]
*[[Основная теорема арифметики]]
*[[Дискретная математика, алгоритмы и структуры данных#Комбинаторика | Комбинаторика]]

== Источники информации ==
* Маврин П.Ю. — Лекция по алгоритмам над простыми числами (2016)
* [https://ru.wikipedia.org/wiki/Простое_число https://ru.wikipedia.org/wiki/Простое_число]

[[Категория: Алгоритмы алгебры и теории чисел]]
[[Категория: Теория чисел]]

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

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