Изменения

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

{{Определение | definition==Проверка ''Перебор делителей'' — алгоритм факторизации или тестирования простоты числа на простоту за <tex>O(\sqrt{nпутем полного перебора всех возможных потенциальных делителей.}})</tex>==

Обычно перебор == Перебор делителей заключается в переборе всех целых ===== Наивная реализация <tex>O(как вариант: простыхn) чисел от 2 до квадратного корня из факторизуемого числа ''</tex><font color=white>O(n'' и )</font> ======= Основная идея ====[[Основная теорема арифметики#Основная теорема арифметики#Собственно теорема | Основная теорема арифметики]], в вычислении остатка от деления ''n'' на каждое из этих чиселкупе с утверждением, что <tex>\forall x, y \in \mathbb{N}~~x<y \Longrightarrow</tex> {{Acronym|<tex>\left( \dfrac{x}{y} < 1 \right)</tex>|т. Если остаток от деления на некоторое число ''m'' равен нулю, то ''m'' является делителем ''n''е. В этом случае либо ''n'' объявляется составным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>''' <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> <font color=green>// проверены все множители из [2; probe]</font> probe++ '''else''' <font color=green>// делим пока делится</font> curNum /= probe result += [probe] '''return''' result</code>==== Псевдокод нахождения делителей ====<code> '''function''' <tex>\mathrm{getDividers}</tex>(number: '''int'''): '''vector<int>''' <font color=green>// массив полученных делителей</font> result = '''vector<int>''' <font color=green>// перебираем все потенциальные делители</font> '''for''' probe = 2 '''to''' number '''if''' number '''mod''' probe = 0 <font color=green>// probe делит number нацело</font> result += [probe] '''return''' result</code>=== Улучшенная реализация <tex>O(\sqrt{n})</tex> и перебирая не более <font color=white>O(√n)</font> ======= Основная идея ====Из определения: <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>O(<tex>\mathtt{number}</tex>: '''int'''): '''vector<int>''' result = '''vector<int>''' '''for''' probe = 2 '''to''' <tex>\sqrt{n\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</code>=== Проверка числа на простоту. Множители ===Алгоритм можно переделать для нахождения простых чисел. Число будет простым, если у него не окажется {{Acronym|множителей|и делителей}}кроме 1 (алгоритмы не проверяют делимость на 1)и самого числа (улучшенная реализация опускает этот делитель). Исключительный случай: <tex>\mathtt{number} = 2</tex>.

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

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