Факторизация за корень

Факторизация за $O(\sqrt{N})$

Базовая теория

Любое натуральное число можно разложить на произведение простых (об этом говорит основная теорма арифметики), и с такой записью очень легко работать при решении задач.

Определение:
Факторизация —это разложение на простые множители

Примеры: $$11 = 11 = 11^1$$ $$100 = 2 \times 2 \times 5 \times 5 = 2^2 \times 5^2$$ $$126 = 2 \times 3 \times 3 \times 7 = 2^1 \times 3^2 \times 7^1$$ Рассмотрим такую задачу:

Условие: Нужно разбить $N$ людей на группы равного размера. Нам интересно, какие размеры это могут быть и сколькими способами это можно сделать.

Решение: По сути нас просят найти число различных делителей $N$. Нужно посмотреть на разложение числа $N$ на простые множители, в общем виде оно выглядит так:

$$N= p_1^{a_1} \times p_2^{a_2} \times \ldots \times p_k^{a_k}$$

Теперь подумаем над этим выражением с точки зрения комбинаторики. Чтобы «сгенерировать» какой-нибудь делитель, нужно подставить в степень $i$-го простого число от 0 до $a_i$ (то есть $a_i+1$ различное значение), и так для каждого. То есть делитель $N$ выглядит ровно так: $$M= p_1^{b_1} \times p_2^{b_2} \times \ldots \times p_k^{b_k}, \ \ 0 \leq b_i \leq a_i$$ Значит, ответом будет произведение $(a_1+1) \times (a_2+1) \times \ldots \times (a_k + 1)$.

Описание алгоритма

Применяя алгоритм проверки числа на простоту, мы умеем легко находить минимальный простой делитель числа N. Ясно, что как только мы нашли простой делитель числа $N$, мы можем число $N$ на него поделить и продолжить искать новый минимальный простой делитель.

Будем перебирать простой делитель от $2$ до корня из $N$ (как и раньше), но в случае, если $N$ делится на этот делитель, будем просто на него делить. Причем, возможно, нам понадобится делить несколько раз ($N$ может делиться на большую степень этого простого делителя). Так мы будем набирать простые делители и остановимся в тот момент, когда $N$ стало либо $1$, либо простым (и мы остановились, так как дошли до корня из него). Во втором случае надо еще само $N$ добавить в ответ.

 1 vector<int> factorize(int N) {
 2     vector<int> result;
 3     for (int i = 2; i * i <= N; i++) {
 4         while (N % i == 0) {
 5             result.push_back(i);
 6             N /= i;
 7         }
 8     }
 9     if (N != 1) {
10         result.push_back(N);
11     }
12     return result;
13 }

Асимптотика

Заметим, что итераций цикла for будет не более $\bigl\lceil\sqrt{N}\bigr\rceil$, то есть $O\left(\sqrt{N}\right)$. При делении на какое-то простое число $N$ уменьшается хотя бы в два раза, поэтому суммарное число итераций цикла while не превосходит $\log N$. Значит, весь алгоритм работает за $O\left(\log N + \sqrt{N}\right) = O\left(\sqrt{N}\right)$.

---

Автор конспекта: Полина Романченко

По всем вопросам пишите в telegram @Romanchenko