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

Материал из Викиконспекты
Перейти к: навигация, поиск
(дефисы заменить на тире, там же должно быть тире, английские термины, сделать псевдокод одинаковым во всех частях статьи)
(Метки: правка с мобильного устройства, правка из мобильной версии)
м (rollbackEdits.php mass rollback)
 
(не показаны 42 промежуточные версии 6 участников)
Строка 1: Строка 1:
 
{{Определение | definition=
 
{{Определение | definition=
''Факторизация'' (англ. ''factorization'') — представление объекта в виде произведения других объектов.
+
'''Факторизация''' (англ. ''factorization'') — представление объекта в виде произведения других объектов.
 
}}
 
}}
 
{{Определение | definition=
 
{{Определение | definition=
''Разложение на множители'', или ''Факторизация целых чисел'' (англ. ''integer factorization'') — представление числа в виде [[Основная теорема арифметики#Основная теорема арифметики#Собственно теорема | произведения его множителей]].
+
'''Разложение на множители''', или '''Факторизация целых чисел''' (англ. ''integer factorization'') — представление числа в виде [[Натуральные числа#Основная теорема арифметики | произведения его множителей]].
 
}}
 
}}
 +
== Перебор делителей==
 
{{Определение | definition=
 
{{Определение | definition=
''Перебор делителей'' — алгоритм факторизации или тестирования простоты числа путем полного перебора всех возможных потенциальных делителей.
+
'''Перебор делителей''' (англ. ''Trial division'') — алгоритм для факторизации или тестирования простоты числа путем полного перебора всех возможных потенциальных делителей.
 
}}
 
}}
 
+
=== Наивная реализация O(n) ===
== Перебор делителей (англ. ''Trial division'')==
+
[[Основная теорема арифметики#Основная теорема арифметики#Собственно теорема | Основная теорема арифметики]], вкупе с утверждением, что  <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> ===
 
 
==== Основная идея ====
 
==== Основная идея ====
[[Основная теорема арифметики#Основная теорема арифметики#Собственно теорема | Основная теорема арифметики]], в купе с утверждением, что <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''' getMultipliers(number: '''int'''): '''vector<int>'''
 
   '''function''' getMultipliers(number: '''int'''): '''vector<int>'''
 
       <font color=green>// сюда складываем множители</font>
 
       <font color=green>// сюда складываем множители</font>
Строка 26: Строка 25:
 
       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++
Строка 34: Строка 33:
 
               result += [probe]
 
               result += [probe]
 
         '''return''' result
 
         '''return''' result
</code>
+
 
 
==== Псевдокод нахождения делителей ====
 
==== Псевдокод нахождения делителей ====
<code>
+
 
 
     '''function''' getDividers(number: '''int'''): '''vector<int>'''
 
     '''function''' getDividers(number: '''int'''): '''vector<int>'''
 
         <font color=green>// массив полученных делителей</font>
 
         <font color=green>// массив полученных делителей</font>
Строка 46: Строка 45:
 
                 result += [probe]
 
                 result += [probe]
 
         '''return''' result
 
         '''return''' result
</code>
+
 
 
=== Улучшенная реализация <tex>O(\sqrt{n})</tex> ===
 
=== Улучшенная реализация <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 = number</tex>
+
|<tex>x \cdot y = number</tex>
 
|rowspan="2"| <tex>\Longrightarrow x > \sqrt{number}</tex>  
 
|rowspan="2"| <tex>\Longrightarrow x > \sqrt{number}</tex>  
 
|-align="center"
 
|-align="center"
Строка 60: Строка 59:
 
Таким образом, любой делитель <tex>d_0 > \sqrt{number}</tex> однозначно связан с некоторым <tex>d_1 < \sqrt{number}</tex>. Если мы найдем все делители до <tex>\sqrt{number}</tex>, задача может считаться решенной.
 
Таким образом, любой делитель <tex>d_0 > \sqrt{number}</tex> однозначно связан с некоторым <tex>d_1 < \sqrt{number}</tex>. Если мы найдем все делители до <tex>\sqrt{number}</tex>, задача может считаться решенной.
 
==== Псевдокод ====
 
==== Псевдокод ====
<code>
+
 
     '''function''' getDividers</tex>(number: '''int'''): '''vector<int>'''
+
     '''function''' getDividers(number: '''int'''): '''vector<int>'''
 
         result = '''vector<int>'''
 
         result = '''vector<int>'''
         '''for''' probe = 2 '''to''' <tex>\sqrt{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 += [number / probe] <font color=green>// <--- записываем сопряженный делитель</font>
+
                 result += [number / probe] <font color=green>// записываем сопряженный делитель</font>
 
         '''return''' result
 
         '''return''' result
</code>
 
=== Проверка числа на простоту. Множители ===
 
Алгоритм можно переделать для нахождения простых чисел. Число будет простым, если у него не окажется {{Acronym|множителей|и делителей}} кроме 1 (алгоритмы не проверяют делимость на 1) и самого числа (улучшенная реализация опускает этот делитель). Исключительный случай: <tex>number = 2</tex>.
 
  
Вообще говоря, представленный выше алгоритм <tex>\mathrm{getMultipliers}</tex> ищет простые множители. Чтобы получить разложения на множители необходимо реализовать [[Генерация комбинаторных объектов в лексикографическом порядке|перебор разбиений]] мультимножества простых множителей на подмножества, тогда, перемножив элементы подмножеств, мы получим множители.  
+
=== Проверка числа на простоту ===
 +
Алгоритм можно переделать для нахождения простых чисел. Число будет простым, если у него не окажется множителей (и делителей) кроме <tex>1</tex> (алгоритмы не проверяют делимость на <tex>1</tex>) и самого числа (улучшенная реализация опускает этот делитель).
 +
 
 
== Предподсчет ==
 
== Предподсчет ==
 
{{main|Решето Эратосфена}}
 
{{main|Решето Эратосфена}}
Строка 78: Строка 76:
 
Решето Эратосфена (англ. ''Sieve of Eratosthenes'') позволяет не только находить простые числа, но и находить простые множители числа. Для этого необходимо хранить (помимо самого "решета") массив простых чисел, на которое каждое число делится (достаточно одного простого делителя).
 
Решето Эратосфена (англ. ''Sieve of Eratosthenes'') позволяет не только находить простые числа, но и находить простые множители числа. Для этого необходимо хранить (помимо самого "решета") массив простых чисел, на которое каждое число делится (достаточно одного простого делителя).
 
=== Псевдокод ===
 
=== Псевдокод ===
<code>
+
 
 
     <font color=green>// возвращает только дополнительный массив</font>
 
     <font color=green>// возвращает только дополнительный массив</font>
     '''function''' sieveOfEratosthenes(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{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>i^2</tex>
 
                 shuttle = <tex>i^2</tex>
Строка 100: Строка 99:
 
         // делением предыдущего на простой делитель из решета</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)
 
* [https://ru.wikipedia.org/wiki/Простое_число https://ru.wikipedia.org/wiki/Простое_число]
 
  
 
== См. также ==
 
== См. также ==
Строка 115: Строка 108:
 
*[[Основная теорема арифметики]]
 
*[[Основная теорема арифметики]]
 
*[[Дискретная математика, алгоритмы и структуры данных#Комбинаторика | Комбинаторика]]
 
*[[Дискретная математика, алгоритмы и структуры данных#Комбинаторика | Комбинаторика]]
 +
 +
== Источники информации ==
 +
* Маврин П.Ю. — Лекция по алгоритмам над простыми числами (2016)
 +
* [https://ru.wikipedia.org/wiki/Простое_число https://ru.wikipedia.org/wiki/Простое_число]
  
 
[[Категория: Алгоритмы алгебры и теории чисел]]
 
[[Категория: Алгоритмы алгебры и теории чисел]]
 +
[[Категория: Теория чисел]]

Текущая версия на 19:17, 4 сентября 2022

Определение:
Факторизация (англ. 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

См. также

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