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

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

Факторизация - представление объекта в виде произведения других объектов.

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

Разложение на множители, или Факторизация целых чисел - представление числа в виде произведения его множителей.

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

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

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

Наивная реализация [math]O(n)[/math]O(n)

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

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

Заметим, что если [math]\mathtt{number} = \prod p_i = p_1 * p_2 * \dots * p_{j-1} * p_j * p_{j+1} * \dots * p_n[/math], то [math]\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[/math]. Таким образом, мы можем делить [math]\mathtt{number}[/math] на его делители последовательно и в любом порядке. Тогда будем хранить [math]\mathtt{curNum} \colon \mathtt{curNum} * \prod \mathtt{result_i} =\mathtt{number}[/math] - произведение оставшихся множителей.

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

Алгоритм работает за [math]O(k)[/math], где k - количество простых множителей.

  function [math]\mathrm{getMultipliers}[/math](number: int): vector<int>
      // сюда складываем множители
      result = vector<int>
      // число, у которого осталось найти множители; 
      curNum = number
       // число, на которое пытаемся делить
      probe = 2
      while curNum [math]\ne[/math] 1
          if curNum mod probe [math]\ne 0[/math]
              // проверены все множители из [2; probe]
              probe++
          else
              // делим пока делится
              curNum /= probe
              result += [probe]
       return result

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

   function [math]\mathrm{getDividers}[/math](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]O(√n)

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

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

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

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

Псевдокод

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

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

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

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

Предподсчет

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

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

Псевдокод

   // возвращает только дополнительный массив
   function [math]\mathrm{sieveOfEratosthenes}[/math](n: int): int[n]
       result = [n]
       // выбираем следующий простой делитель
       for i = 2 to [math]\sqrt{\mathtt{n}}[/math]
           if result[i] [math]\ne[/math] null
               // записываем делитель в элементы массива,
               // соответствующие числа которых делятся нацело
               shuttle = [math]\mathtt{i}^2[/math]
               while shuttle [math]\leqslant[/math] n
                   result[shuttle] = i
                   shuttle += i
       return result

   function [math]\mathrm{getMultipliers}[/math](number: int): vector<int>
       result = vector<int>
       // получаем дополненное решето Эратосфена
       sieve = [math]\mathrm{sieveOfEratosthenes}[/math](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/Простое_число