Разложение на множители (факторизация) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Перебор делителей)
(не показаны 42 промежуточные версии 5 участников)
Строка 1: Строка 1:
 
{{Определение | definition=
 
{{Определение | definition=
''Факторизация'' - представление объекта в виде произведения других объектов.
+
'''Факторизация''' (англ. ''factorization'') — представление объекта в виде произведения других объектов.
 
}}
 
}}
 
{{Определение | definition=
 
{{Определение | definition=
''Разложение на множители'', или ''Факторизация целых чисел'' - представление числа в виде [[Основная теорема арифметики#Основная теорема арифметики#Собственно теорема | произведения его множителей]].
+
'''Разложение на множители''', или '''Факторизация целых чисел''' (англ. ''integer factorization'') — представление числа в виде [[Натуральные числа#Основная теорема арифметики | произведения его множителей]].
 
}}
 
}}
 
+
== Перебор делителей==
 
{{Определение | definition=
 
{{Определение | 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>O(n)</tex><font color=white>O(n)</font> ===
 
 
==== Основная идея ====
 
==== Основная идея ====
[[Основная теорема арифметики#Основная теорема арифметики#Собственно теорема | Основная теорема арифметики]], в купе с утверждением, что <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>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>\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 - количество простых множителей.
+
Так как простых множителей не может быть больше, чем <tex>n</tex>, а в худшем случае (когда число простое, и на каждое итерации <tex>probe</tex> увеличивается на <tex>1</tex>) он работает за <tex>O(n)</tex>, то, следовательно, алгоритм работает за <tex>O(n)</tex>.
<code>
+
 
   '''function''' <tex>\mathrm{getMultipliers}</tex>(number: '''int'''): '''vector<int>'''
+
   '''function''' getMultipliers(number: '''int'''): '''vector<int>'''
 
       <font color=green>// сюда складываем множители</font>
 
       <font color=green>// сюда складываем множители</font>
 
       result = '''vector<int>'''
 
       result = '''vector<int>'''
       <font color=green>// число, у которого осталось найти множители; </font>
+
       <font color=green>// число, у которого осталось найти множители</font>
 
       curNum = number
 
       curNum = number
 
         <font color=green>// число, на которое пытаемся делить</font>
 
         <font color=green>// число, на которое пытаемся делить</font>
 
       probe = 2
 
       probe = 2
 
       '''while''' curNum <tex>\ne</tex> 1
 
       '''while''' curNum <tex>\ne</tex> 1
           '''if''' curNum '''mod''' probe <tex>\ne 0</tex>
+
           '''if''' curNum '''mod''' probe <tex>\ne\, </tex>0
 
               <font color=green>// проверены все множители из [2; probe]</font>
 
               <font color=green>// проверены все множители из [2; probe]</font>
 
               probe++
 
               probe++
Строка 35: Строка 33:
 
               result += [probe]
 
               result += [probe]
 
         '''return''' result
 
         '''return''' result
</code>
+
 
 
==== Псевдокод нахождения делителей ====
 
==== Псевдокод нахождения делителей ====
<code>
+
 
     '''function''' <tex>\mathrm{getDividers}</tex>(number: '''int'''): '''vector<int>'''
+
     '''function''' getDividers(number: '''int'''): '''vector<int>'''
 
         <font color=green>// массив полученных делителей</font>
 
         <font color=green>// массив полученных делителей</font>
 
         result = '''vector<int>'''  
 
         result = '''vector<int>'''  
Строка 47: Строка 45:
 
                 result += [probe]
 
                 result += [probe]
 
         '''return''' result
 
         '''return''' result
</code>
+
 
=== Улучшенная реализация <tex>O(\sqrt{n})</tex><font color=white>O(√n)</font> ===
+
=== Улучшенная реализация <tex>O(\sqrt{n})</tex> ===
 
==== Основная идея ====
 
==== Основная идея ====
Из определения: <tex>\sqrt{n} * \sqrt{n} = n</tex>. Логично, что:
+
Из определения: <tex>\sqrt{n} \cdot \sqrt{n} = n</tex>. Логично, что:
 
{|
 
{|
 
|-align="center"
 
|-align="center"
 
|rowspan="2"| <tex>\bigg\{</tex>
 
|rowspan="2"| <tex>\bigg\{</tex>
|<tex>x * y = \mathtt{number}</tex>
+
|<tex>x \cdot y = number</tex>
|rowspan="2"| <tex>\Longrightarrow x > \sqrt{\mathtt{number}}</tex>  
+
|rowspan="2"| <tex>\Longrightarrow x > \sqrt{number}</tex>  
 
|-align="center"
 
|-align="center"
|<tex>y < \sqrt{\mathtt{number}}</tex>
+
|<tex>y < \sqrt{number}</tex>
 
|}
 
|}
Таким образом, любой делитель <tex>d_0 > \sqrt{\mathtt{number}}</tex> однозначно связан с некоторым <tex>d_1 < \sqrt{\mathtt{number}}</tex>. Если мы найдем все делители до <tex>\sqrt{\mathtt{number}}</tex>, задача может считаться решенной.
+
Таким образом, любой делитель <tex>d_0 > \sqrt{number}</tex> однозначно связан с некоторым <tex>d_1 < \sqrt{number}</tex>. Если мы найдем все делители до <tex>\sqrt{number}</tex>, задача может считаться решенной.
 
==== Псевдокод ====
 
==== Псевдокод ====
<code>
+
 
     '''function''' <tex>\mathrm{getDividers}</tex>(<tex>\mathtt{number}</tex>: '''int'''): '''vector<int>'''
+
     '''function''' getDividers(number: '''int'''): '''vector<int>'''
 
         result = '''vector<int>'''
 
         result = '''vector<int>'''
         '''for''' probe = 2 '''to''' <tex>\sqrt{\mathtt{number}}</tex> <font color=green>// <--- обновляем верхнюю границу перебора</font>
+
         '''for''' probe = 2 '''to''' <tex>\sqrt{number}</tex> <font color=green>//обновляем верхнюю границу перебора</font>
 
             '''if''' number '''mod''' probe = 0
 
             '''if''' number '''mod''' probe = 0
 
                 result += [probe]
 
                 result += [probe]
                 result += [<tex>\mathtt{number}</tex> / probe] <font color=green>// <--- записываем сопряженный делитель</font>
+
                 result += [number / probe] <font color=green>// записываем сопряженный делитель</font>
 
         '''return''' result
 
         '''return''' result
</code>
 
=== Проверка числа на простоту. Множители ===
 
Алгоритм можно переделать для нахождения простых чисел. Число будет простым, если у него не окажется {{Acronym|множителей|и делителей}} кроме 1 (алгоритмы не проверяют делимость на 1) и самого числа (улучшенная реализация опускает этот делитель). Исключительный случай: <tex>\mathtt{number} = 2</tex>.
 
  
Вообще говоря, представленный выше алгоритм <tex>\mathrm{getMultipliers}</tex> ищет простые множители. Чтобы получить разложения на множители необходимо реализовать [[Генерация комбинаторных объектов в лексикографическом порядке|перебор разбиений]] мультимножества простых множителей на подмножества, тогда, перемножив элементы подмножеств, мы получим множители.  
+
=== Проверка числа на простоту ===
 +
Алгоритм можно переделать для нахождения простых чисел. Число будет простым, если у него не окажется множителей (и делителей) кроме <tex>1</tex> (алгоритмы не проверяют делимость на <tex>1</tex>) и самого числа (улучшенная реализация опускает этот делитель).
 +
 
 
== Предподсчет ==
 
== Предподсчет ==
 
{{main|Решето Эратосфена}}
 
{{main|Решето Эратосфена}}
 
=== Основная идея ===
 
=== Основная идея ===
Решето Эратосфена позволяет не только находить простые числа, но и находить простые множители числа. Для этого необходимо хранить (помимо самого "решета") массив простых чисел, на которое каждое число делится (достаточно одного простого делителя).
+
Решето Эратосфена (англ. ''Sieve of Eratosthenes'') позволяет не только находить простые числа, но и находить простые множители числа. Для этого необходимо хранить (помимо самого "решета") массив простых чисел, на которое каждое число делится (достаточно одного простого делителя).
 
=== Псевдокод ===
 
=== Псевдокод ===
<code>
+
 
 
     <font color=green>// возвращает только дополнительный массив</font>
 
     <font color=green>// возвращает только дополнительный массив</font>
     '''function''' <tex>\mathrm{sieveOfEratosthenes}</tex>(n: '''int'''): '''int[n]'''
+
     '''function''' sieveOfEratosthenes(n: '''int'''): '''int'''[n + 1]
         result = [n]
+
         result = [n + 1]
 +
        result[n] = n
 
         <font color=green>// выбираем следующий простой делитель</font>
 
         <font color=green>// выбираем следующий простой делитель</font>
         '''for''' i = 2 '''to''' <tex>\sqrt{\mathtt{n}}</tex>
+
         '''for''' i = 2 '''to''' <tex>\sqrt{n}</tex>
             '''if''' result[i] <tex>\ne</tex> ''null''
+
             '''if''' result[i] = 0
                 <font color=green>// {{Acronym|записываем |в этой реализации и переписываем тоже}}делитель в элементы массива,
+
                 <font color=green>// записываем делитель в элементы массива,
 
                 // соответствующие числа которых делятся нацело</font>
 
                 // соответствующие числа которых делятся нацело</font>
                 shuttle = <tex>\mathtt{i}^2</tex>
+
                 shuttle = <tex>i^2</tex>
 
                 '''while''' shuttle <tex>\leqslant</tex> n
 
                 '''while''' shuttle <tex>\leqslant</tex> n
 
                     result[shuttle] = i
 
                     result[shuttle] = i
Строка 94: Строка 92:
 
         '''return''' result
 
         '''return''' result
  
     '''function''' <tex>\mathrm{getMultipliers}</tex>(number: '''int'''): '''vector<int>'''
+
     '''function''' getMultipliers(number: '''int'''): '''vector<int>'''
 
         result = '''vector<int>'''
 
         result = '''vector<int>'''
 
         <font color=green>// получаем дополненное решето Эратосфена</font>
 
         <font color=green>// получаем дополненное решето Эратосфена</font>
         sieve = <tex>\mathrm{sieveOfEratosthenes}</tex>(number)
+
         sieve = sieveOfEratosthenes(number)
 
         <font color=green>// следующее временное значение получаем
 
         <font color=green>// следующее временное значение получаем
 
         // делением предыдущего на простой делитель из решета</font>
 
         // делением предыдущего на простой делитель из решета</font>
 
         curNum = number
 
         curNum = number
         '''while''' sieve[curNum] <tex>\ne</tex> ''null''
+
         '''while''' curNum <tex>\ne</tex> 1
             result += [sieveNum]
+
             result += sieve[curNum]
 
             curNum /= sieve[curNum]
 
             curNum /= sieve[curNum]
        result += [curNum]
 
 
         '''return''' result
 
         '''return''' result
</code>
+
 
 
== См. также ==
 
== См. также ==
 
*[[Решето Эратосфена]]
 
*[[Решето Эратосфена]]
 
*[[Основная теорема арифметики]]
 
*[[Основная теорема арифметики]]
 
*[[Дискретная математика, алгоритмы и структуры данных#Комбинаторика | Комбинаторика]]
 
*[[Дискретная математика, алгоритмы и структуры данных#Комбинаторика | Комбинаторика]]
 +
 
== Источники информации ==
 
== Источники информации ==
* Маврин П.Ю. - Лекция по алгоритмам над простыми числами (2016)
+
* Маврин П.Ю. Лекция по алгоритмам над простыми числами (2016)
 
* [https://ru.wikipedia.org/wiki/Простое_число https://ru.wikipedia.org/wiki/Простое_число]
 
* [https://ru.wikipedia.org/wiki/Простое_число https://ru.wikipedia.org/wiki/Простое_число]
 +
 
[[Категория: Алгоритмы алгебры и теории чисел]]
 
[[Категория: Алгоритмы алгебры и теории чисел]]
 +
[[Категория: Теория чисел]]

Версия 09:02, 10 июня 2021

Определение:
Факторизация (англ. factorization) — представление объекта в виде произведения других объектов.


Определение:
Разложение на множители, или Факторизация целых чисел (англ. integer factorization) — представление числа в виде произведения его множителей.

Перебор делителей

Определение:
Перебор делителей (англ. Trial division) — алгоритм для факторизации или тестирования простоты числа путем полного перебора всех возможных потенциальных делителей.

Наивная реализация O(n)

Основная теорема арифметики, вкупе с утверждением, что [math]y[/math] не делит [math]x[/math] нацело: [math]\forall x, y \in \mathbb{N}~~x\lt y \Longrightarrow[/math] [math]\left( \dfrac{x}{y} \lt 1 \right)[/math], позволяют нам ограничить пространство поиска делителей числа [math]number[/math] интервалом [math][2;number][/math].

Основная идея

Заметим, что если [math]number[/math] = [math]\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[/math], то [math]\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[/math]. Таким образом, мы можем делить [math]number[/math] на его делители (множители) последовательно и в любом порядке. Тогда будем хранить [math]curNum \colon curNum = \dfrac{number}{\prod result_i}[/math] — произведение оставшихся множителей.

Псевдокод нахождения простых множителей

Так как простых множителей не может быть больше, чем [math]n[/math], а в худшем случае (когда число простое, и на каждое итерации [math]probe[/math] увеличивается на [math]1[/math]) он работает за [math]O(n)[/math], то, следовательно, алгоритм работает за [math]O(n)[/math].

  function getMultipliers(number: int): vector<int>
      // сюда складываем множители
      result = vector<int>
      // число, у которого осталось найти множители
      curNum = number
       // число, на которое пытаемся делить
      probe = 2
      while curNum [math]\ne[/math] 1
          if curNum mod probe [math]\ne\, [/math]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

Улучшенная реализация [math]O(\sqrt{n})[/math]

Основная идея

Из определения: [math]\sqrt{n} \cdot \sqrt{n} = n[/math]. Логично, что:

[math]\bigg\{[/math] [math]x \cdot y = number[/math] [math]\Longrightarrow x \gt \sqrt{number}[/math]
[math]y \lt \sqrt{number}[/math]

Таким образом, любой делитель [math]d_0 \gt \sqrt{number}[/math] однозначно связан с некоторым [math]d_1 \lt \sqrt{number}[/math]. Если мы найдем все делители до [math]\sqrt{number}[/math], задача может считаться решенной.

Псевдокод

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

Проверка числа на простоту

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

Предподсчет

Основная статья: Решето Эратосфена

Основная идея

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

Псевдокод

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

См. также

Источники информации