Изменения

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

Обычно перебор делителей заключается в переборе всех целых '''function''' getMultipliers(как вариантnumber: простых'''int''') чисел от : '''vector<int>''' <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 ''n'if' и в вычислении остатка от деления ''ncurNum '' на каждое из этих чисел. Если остаток от деления на некоторое число 'mod'm'' равен нулюprobe <tex>\ne\, то </tex>0 <font color=green>// проверены все множители из [2; probe]</font> probe++ ''m'else' является делителем ''n <font color=green>// делим пока делится</font> curNum /= probe result += [probe] ''. В этом случае либо 'return'n'' объявляется составным, и алгоритм заканчивает работу.result

'''function''' getDividers(number: '''int'''): '''vector<int>''' <font color=green>// массив полученных делителей</font> result =Разложение на множители за '''vector<texint>O(\sqrt{n})''' <font color=green>// перебираем все потенциальные делители</texfont> '''for''' probe =2 '''to''' number '''if''' number '''mod''' probe = 0 <font color=green>// probe делит number нацело</font> result +=[probe] '''return''' result

Для поиска разложения числа на множители воспользуемся так же простым перебором чисел от === Улучшенная реализация <tex>1O(\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>md_0 > \sqrt{number}</tex> числа однозначно связан с некоторым <tex>nd_1 < \sqrt{number}</tex>. Далее Если мы найдем все делители до <tex>\sqrt{number}</tex>n, задача может считаться решенной.==== Псевдокод ====  '''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 === Проверка числа на простоту ===Алгоритм можно переделать для нахождения простых чисел. Число будет простым, если у него не окажется множителей (и делителей) кроме <tex>1</tex> сокращается в (алгоритмы не проверяют делимость на <tex>m1</tex> раз ) и самого числа (улучшенная реализация опускает этот делитель). == Предподсчет =={{main|Решето Эратосфена}}=== Основная идея ===Решето Эратосфена (англ. ''Sieve of Eratosthenes'') позволяет не только находить простые числа, но и процедура повторяетсянаходить простые множители числа. Для этого необходимо хранить (помимо самого "решета") массив простых чисел, на которое каждое число делится (достаточно одного простого делителя). По достижении квадратного корня из === Псевдокод ===  <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] = 0 <font color=green>// записываем делитель в элементы массива, // соответствующие числа которых делятся нацело</font> 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>''' <font color=green>/tex/ получаем дополненное решето Эратосфена</font> sieve = sieveOfEratosthenes(number) <font color=green> ни // следующее временное значение получаем // делением предыдущего на одно простой делитель из меньших чисел, решета</font> curNum = number '''while''' curNum <tex>n\ne</tex> объявляется неразложимым1 result += sieve[curNum] curNum /= sieve[curNum] '''return''' result == См. также ==*[[Решето Эратосфена]]*[[Основная теорема арифметики]]*[[Дискретная математика, алгоритмы и структуры данных#Комбинаторика | Комбинаторика]] == Источники информации ==* Маврин П.Ю. — Лекция по алгоритмам над простыми числами (2016)* [https://ru.wikipedia.org/wiki/Простое_число https://ru.wikipedia.org/wiki/Простое_число] [[Категория: Алгоритмы алгебры и теории чисел]][[Категория: Теория чисел]]