Разложение на множители (факторизация)

Определение:

Факторизация (англ. 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] интервалом [2; [math]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]O(k)[/math], где [math]k[/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]) и самого числа (улучшенная реализация опускает этот делитель). Исключительный случай: [math]number = 2[/math].

Вообще говоря, представленный выше алгоритм [math]\mathrm{getMultipliers}[/math] ищет простые множители. Чтобы получить разложения на множители необходимо реализовать перебор разбиений мультимножества простых множителей на подмножества, тогда, перемножив элементы подмножеств, мы получим множители.

Предподсчет

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

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

Псевдокод

   // возвращает только дополнительный массив
   function sieveOfEratosthenes(n: int): int[n]
       result = [n]
       // выбираем следующий простой делитель
       for i = 2 to [math]\sqrt{n}[/math]
           if result[i] [math]\ne[/math] null
               // записываем делитель в элементы массива,
               // соответствующие числа которых делятся нацело
               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 sieve[curNum] [math]\ne[/math] null
           result += [sieveNum]
           curNum /= sieve[curNum]
       result += [curNum]
       return result

См. также

• Решето Эратосфена
• Основная теорема арифметики
• Комбинаторика

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

• Маврин П.Ю. — Лекция по алгоритмам над простыми числами (2016)
• https://ru.wikipedia.org/wiki/Простое_число