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

Материал из Викиконспекты
Перейти к: навигация, поиск
Определение:
Факторизация - представление объекта в виде произведения других объектов.


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


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


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

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

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

Основная теорема арифметики, в купе с утверждением, что [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]

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

Из определения: [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

См. также

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