1632
правки
Изменения
м
Алгоритм Так как простых множителей не может быть больше, чем <tex>n</tex>, а в худшем случае (когда число простое, и на каждое итерации <tex>probe</tex> увеличивается на <tex>1</tex>) он работает за <tex>O(kn)</tex>, где то, следовательно, алгоритм работает за <tex>kO(n)</tex> — количество простых множителей.
result += [curNum]
rollbackEdits.php mass rollback
}}
{{Определение | 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; <tex>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> — произведение оставшихся множителей.
==== Псевдокод нахождения простых множителей ====
'''function''' getMultipliers(number: '''int'''): '''vector<int>'''
'''function''' getDividers(number: '''int'''): '''vector<int>'''
result = '''vector<int>'''
'''for''' probe = 2 '''to''' <tex>\sqrt{number}</tex> <font color=green>// <--- обновляем верхнюю границу перебора</font> '''if''' number '''mod ''' probe = 0
result += [probe]
result += [number / probe] <font color=green>// <--- записываем сопряженный делитель</font>
'''return''' result
=== Проверка числа на простоту. Множители ===Алгоритм можно переделать для нахождения простых чисел. Число будет простым, если у него не окажется {{Acronym|множителей|(и делителей}} ) кроме <tex>1</tex> (алгоритмы не проверяют делимость на <tex>1</tex>) и самого числа (улучшенная реализация опускает этот делитель). Исключительный случай: <tex>number = 2</tex>. Вообще говоря, представленный выше алгоритм <tex>\mathrm{getMultipliers}</tex> ищет простые множители. Чтобы получить разложения на множители необходимо реализовать [[Генерация комбинаторных объектов в лексикографическом порядке|перебор разбиений]] мультимножества простых множителей на подмножества, тогда, перемножив элементы подмножеств, мы получим множители.
== Предподсчет ==
<font color=green>// возвращает только дополнительный массив</font>
'''function''' sieveOfEratosthenes(n: '''int'''): '''int'''[n+ 1] result = [n+ 1] result[n] = n
<font color=green>// выбираем следующий простой делитель</font>
'''for''' i = 2 '''to''' <tex>\sqrt{n}</tex> '''if''' result[i] <tex>\ne</tex> ''null''= 0
<font color=green>// записываем делитель в элементы массива,
// соответствующие числа которых делятся нацело</font>
// делением предыдущего на простой делитель из решета</font>
curNum = number
'''while''' sieve[curNum] <tex>\ne</tex> ''null''1 result += sieve[sieveNumcurNum]
curNum /= sieve[curNum]
'''return''' result
[[Категория: Алгоритмы алгебры и теории чисел]]
[[Категория: Теория чисел]]
