---
tags: number-theory, integer-factorization, sieve, factorial, primes
---

# Factorización de enteros

Ligado a los divisores y a los números primos, la factorización de un entero $n$ nos dice de forma exacta quiénes son todos sus factores primos y la multiplicidad de cada uno. Conocer esta factorización nos da muchísima información sobre el número $n$.

## Teorema fundamental de la aritmética
Sea $n \in \mathbb{N}$, este teorema nos dice que podemos expresar a $n$ como un producto de números primos de forma única, salvo el orden. A la tarea de hallar dicha descomposición, la llamaremos **factorización**.

:::info
:information_source: **Ejemplo:** sea $n=84$. Lo podemos expresar como $84 = 2 \times 2 \times 3 \times 7$, y vemos que $2,3,7$ son todos primos. No hallaremos otra representación así que use otros primos, pues eso lo garantiza el teorema fundamental de la aritmética.

Usualmente agrupamos los primos que se repiten usando exponentes, donde el exponente nos indica su multiplicidad. Por ejemplo: $84 = 2^2 \times 3 \times 7$.
:::

Esta es otra razón por la que los números primos son tan importantes, pues son los bloquecitos más elementales que son capaces de construir a todos los números naturales.

**Observación:** se considera que la factorización en primos del $1$ es el *producto vacío*, pues no tiene factores primos.

## Factorización simple
Un hecho muy importante para el algoritmo que vamos a proponer es que ++el divisor más pequeño de $n$ mayor a 1 tiene que ser un número primo++.

:::spoiler **Demostración**
- Si $n$ es primo ya terminamos, pues su primer divisor más pequeño mayor a $1$ es $n$, y $n$ es primo.
- Si $n$ es compuesto, sea $d$ su divisor más pequeño mayor a 1. Supongamos que $d$ es compuesto, entonces existe $a \in \mathbb{N}$ tal que $a \mid d$ y $1 < a < d$. De esta forma, por transitividad, $a \mid n$, lo cual es una contradicción, pues $a < d$ pero habíamos asumido que $d$ era el más pequeño. Entonces, $d$ tiene que ser primo.
:::

Por lo tanto, hallemos el primer primo $p$ tal que $n=pn'$, entonces metemos $p$ a la lista de factores primos y procedemos a factorizar $n'$ de forma recursiva. Nos detenemos hasta que $n'=1$, pues ya no se puede seguir descomponiendo más.

:::info
:information_source: **Ejemplo:** factoricemos $84$:
- Al principio tenemos nuestra lista vacía de primos $\{\}$.
- El $2$ es el primer primo que divide a $84$, por lo tanto metemos $2$ a la lista: $\{2\}$ y procedemos a factorizar $84/2=42$.
- El $2$ es el primer primo que divide a $42$, por lo tanto metemos $2$ a la lista: $\{2, 2\}$ y procedemos a factorizar $42/2=21$.
- El $3$ es el primer primo que divide a $21$, por lo tanto metemos $3$ a la lista: $\{2, 2, 3\}$ y procedemos a factorizar $21/3=7$.
- El $7$ es el primer primo que divide a $7$, por lo tanto metemos $7$ a la lista: $\{2, 2, 3, 7\}$ y procedemos a factorizar $7/7=1$.
- Como ya llegamos a $1$, terminamos y nuestra lista de factores primos es $\{2, 2, 3, 7\}$, que es lo que ya sabíamos del ejemplo anterior.
:::

Para la implementación se suele programar de forma iterativa: podemos ir iterando todas las $p$'s en el rango $[2, \lfloor \sqrt{n} \rfloor]$, y cada que una divida a $n$, dividir $n$ entre $p$ lo más que se pueda, y continuar. Dicha $p$ está garantizada que será un primo por la propiedad anterior. Al final de estas iteraciones, pueden suceder dos cosas:
- La $n'$ restante a factorizar es igual a $1$, por lo tanto ya hayamos todos los factores primos de la $n$ original.
- La $n'$ restante es diferente de $1$. Eso quiere decir que ningún primo en el rango $[2, \lfloor \sqrt{n} \rfloor]$ la dividió, por lo tanto $n'$ tiene que ser primo y lo añadimos a la lista de factores primos.

La implementación queda de la siguiente manera:

### Algoritmo 1: Factorización de un entero

map<int, int> factorize(int n){
    // Usualmente guardamos pares de la forma (p, e), donde p es el primo y e cuántas veces se repite
    // Podemos usar un vector de pairs o un map para ello
    map<int, int> fact;
    for(int p = 2; p*p <= n; p++){
        if(n % p == 0){ // Encontramos un divisor p no trivial de n, y tiene que ser primo
            int exponent = 0;
            while(n % p == 0){
                // Mientras n sea divisible entre p, contamos cuántas veces lo divide
                n /= p;
                exponent++;
            }
            fact[p] = exponent; // Guardamos el par (p, e) en la lista
        }
    }
    if(n > 1){ // Si llegamos a este punto, la n' restante a factorizar tiene que ser primo, pues ningún primo menor a sqrt(n) la dividió
        fact[n] = 1;
    }
    return fact;
}

Vemos que para cada primo $p$ que vamos encontrando que divide a $n$, dividimos $n$ entre $p$ todas las veces que sea posible, y para factorizar lo que nos quedó, ya no tiene sentido volver a comenzar a checar primos comenzando en $p$, sino en $p+1$.

La complejidad de esta idea es $O(\sqrt{n})$, viable para factorizar números hasta $10^{14}$.

## Factorización optimizada con la criba normal
Podemos optimizar el ciclo `for` de la línea 5, tal que solo itere sobre los números primos $p$ tal que $p^2 \leq n$. Entonces, tendríamos que precalcular con la criba todos los primos hasta $\lfloor \sqrt{MAX} \rfloor$, donde $MAX$ es el máximo número a factorizar, y así logramos reducir la complejidad un poco a $O(\sqrt{n} / \log(n))$, de forma similar al algoritmo 7 de la sección anterior.

## Factorización con la criba de factor primo más pequeño
Tenemos el siguiente problema: tenemos $q$ queries, en donde cada una debemos hallar la factorización de un entero $n_i$ dado. $1 \leq q \leq 10^5$, $1 \leq n_i \leq 10^7$.

Una forma de resolverlo es aplicar el algoritmo anterior para cada query, logrando una complejidad de $O(q\sqrt{n})$, la cual no es lo suficientemente rápida.

Recordemos que ya sabemos cómo calcular la criba del factor primo más pequeño, y como en el algoritmo anterior justamente estamos buscando el primo más pequeño que divide a $n'$ en cada paso, esta criba nos viene de maravilla.

Lo único que hay que cambiar es la forma en la que hallamos el primo tal que $n=pn'$, dicho primo estará precalculado en $lp[n]$. Este precálculo lo tenemos que hacer hasta $MAX$, donde $MAX$ es el máximo valor que nos pueden dar en una query. La implementación queda como:

### Algoritmo 2: factorización de un entero con criba de $lp$

// Precalculamos lp[] hasta el valor máximo antes de llamar a esta función
map<int, int> factorize(int n){
    map<int, int> fact;
    while(n > 1){ // Hallamos los primos de n mientras no sea igual a 1
        int p = lp[n];
        int exponent = 0;
        while(n % p == 0){ // Dividimos n tantas veces entre su factor primo más pequeño como sea posible
            n /= p;
            exponent++;
        }
        fact[p] = exponent;
    }
    return fact;
}

Factorizar un entero de esta manera nos cuesta $O(\log n)$, pues ya sabemos quién es el primo más pequeño que divide a $n'$ en cada paso y no tenemos que andarlo buscando por fuerza bruta.

:::spoiler ¿Por qué esa complejidad?
El peor caso es que $n$ sea un producto de los primeros $k$ primos distintos, por ejemplo, $n = 2 \times 3 \times 5 \times \cdots \times p_k$. La complejidad es entonces $O(k)$. Pero $n = 2 \times 3 \times \cdots \times p_k \geq \underbrace{2 \times 2 \times \cdots \times 2}_{k\text{ veces el 2}} = 2^k$, por lo tanto $k \leq \log_2(n)$, haciendo la complejidad $O(\log_2 n)$.
:::

Por lo tanto, la complejidad total es ahora $O(MAX \log \log MAX + q \log(n))$.

## Observaciones
- Vemos que si tenemos pocas queries y números grandes a factorizar del orden de $10^{14}$, tenemos que usar el algoritmo 1, pues un precálculo con la criba de $lp$ tardaría muchísimo y usaría mucha memoria.
- Si tenemos muchas queries pero los números a factorizar son del orden de $10^7$, nos conviene más un precálculo con la criba de $lp$ y contestar cada query en $O(\log n)$ usando el algoritmo 2.

## Obtener divisores a través de la factorización
La factorización nos ofrece muchísima información sobre el entero $n$, por ahora veamos cómo obtener la lista de todos los divisores de un número $n$ a través de su factorización en primos.

Sea $n={p_1}^{e_1} {p_2}^{e_2} \cdots {p_k}^{e_k}$ dado en su factorización estándar con $k$ primos. Al combinar las potencias de cada primo entre sí, podemos obtener diferentes divisores. De forma específica, por cada primo $p_i$ podemos escoger entre las potencias ${p_i}^0$, ${p_i}^1$, ${p_i}^2$, $\ldots$, ${p_i}^{e_i}$, teniendo $e_i+1$ formas de hacerlo.

:::info
:information_source: **Ejemplo:** queremos hallar los divisores de $n=360$. Sabemos que su factorización en primos es $n=2^3 \times 3^2 \times 5$.
- Para el primo $2$ tenemos 4 opciones para combinar: $\color{red}{[1, 2, 4, 8]}$.
- Para el primo $3$ tenemos 3 opciones para combinar: $\color{green}{[1, 3, 9]}$.
- Para el primo $5$ tenemos 2 opciones para combinar: $[1, 5]$.

De aquí vemos que tenemos un total de $4 \times 3 \times 2 = 24$ formas de multiplicar las potencias de los primos entre sí, y este número es justamente el número de divisores. Ellos son:
1. $\color{red}{1} \times \color{green}{1} \times 1 = 1$
2. $\color{red}{1} \times \color{green}{1} \times 5 = 5$
3. $\color{red}{1} \times \color{green}{3} \times 1 = 3$
4. $\color{red}{1} \times \color{green}{3} \times 5 = 15$
5. $\color{red}{1} \times \color{green}{9} \times 1 = 9$
6. $\color{red}{1} \times \color{green}{9} \times 5 = 45$
7. $\color{red}{2} \times \color{green}{1} \times 1 = 2$
8. $\color{red}{2} \times \color{green}{1} \times 5 = 10$
9. $\color{red}{2} \times \color{green}{3} \times 1 = 6$
10. $\color{red}{2} \times \color{green}{3} \times 5 = 30$
11. $\color{red}{2} \times \color{green}{9} \times 1 = 18$
12. $\color{red}{2} \times \color{green}{9} \times 5 = 90$
13. $\color{red}{4} \times \color{green}{1} \times 1 = 4$
14. $\color{red}{4} \times \color{green}{1} \times 5 = 20$
15. $\color{red}{4} \times \color{green}{3} \times 1 = 12$
16. $\color{red}{4} \times \color{green}{3} \times 5 = 60$
17. $\color{red}{4} \times \color{green}{9} \times 1 = 36$
18. $\color{red}{4} \times \color{green}{9} \times 5 = 180$
19. $\color{red}{8} \times \color{green}{1} \times 1 = 8$
20. $\color{red}{8} \times \color{green}{1} \times 5 = 40$
21. $\color{red}{8} \times \color{green}{3} \times 1 = 24$
22. $\color{red}{8} \times \color{green}{3} \times 5 = 120$
23. $\color{red}{8} \times \color{green}{9} \times 1 = 72$
24. $\color{red}{8} \times \color{green}{9} \times 5 = 360$
:::

Hay varias formas de implementar esta idea. Una de ellas es comenzar con una lista $divs$ con el $1$ como su único elemento. Luego, por cada par ${p_i}^{e_i}$, multiplicamos todos los elementos de $divs$ por ${p_i}^0$, ${p_i}^1$, $\ldots$, ${p_i}^{e_i}$ y los metemos a una nueva lista $divs'$, y al terminar de procesar este primo actualizamos la lista: $divs \gets divs'$.

### Algoritmo 3: divisores a través de factorización

vector<int> getDivsFromFact(const map<int, int> & f){
    vector<int> divs = {1};  // Inicializamos nuestra lista con un 1
    for(auto [p, e] : f){    // Iteramos por cada par (p, e) (esta forma de iterar solo funciona desde C++17)
        vector<int> newDivs; // Nuestra nueva lista de divisores
        int p_pow = 1;       // Aquí iremos calculando de forma iterativa las potencias de p
        for(int i = 0; i <= e; i++){
            for(int d : divs){
                newDivs.push_back(d * p_pow); // Por cada posible potencia de p, multiplicamos cada elemento de la lista de divisores vieja y lo metemos a la nueva
            }
            p_pow *= p;
        }
        divs = newDivs;      // Actualizamos la lista de divisores
    }
    return divs;
}

La complejidad será justamente el número de divisores, que es $(e_1 + 1)(e_2 + 1) \cdots (e_k + 1)$.

## Factorización de un factorial
Definimos al *factorial* de un entero positivo $n$ como $n=1 \times 2 \times \cdots \times n$, y solemos escribir $n!$. Veamos algunos ejemplos con sus factorizaciones en primos:

:::info
:information_source: **Ejemplo:**
- $1! = 1$
- $2! = 1 \times 2 = 2$
- $3! = 1 \times 2 \times 3 = 6 = 2 \times 3$
- $4! = 1 \times 2 \times 3 \times 4 = 24 = 2^3 \times 3$
- $5! = 1 \times 2 \times 3 \times 4 \times 5 = 120 = 2^3 \times 3 \times 5$
- $6! = 1 \times 2 \times 3 \times 4 \times 5 \times 6 = 720 = 2^4 \times 3^2 \times 5$
- $7! = 1 \times 2 \times 3 \times 4 \times 5 \times 6 \times 7 = 5040 = 2^4 \times 3^2 \times 5 \times 7$
:::

El problema que resolveremos es cómo hallar la factorización en primos de $n!$, donde $n \leq 10^7$. Hay varias formas de hacerlo:
- Calcular $n!$ directamente y factorizarlo. Esta opción no es viable, pues crece demasiado rápido y hasta se puede desbordar.
- Llevar un `map` global que guardará la factorización de $n!$, e ir factorizando cada $i$ en el rango $[1, n]$, todo sobre ese mismo `map`.
- Si usamos la factorización que corre en $O(\sqrt{n})$, tendremos una complejidad total de $O(n \sqrt{n})$.
- Si usamos la factorización con la criba de $lp$, la complejidad será de $O(n \log \log n + n \log n)$.
- Sabemos que como $n!$ es el producto de todos los números enteros en el rango $[1,n]$, entonces sus factores primos no van a exceder $n$. Por lo tanto, por cada primo $p \leq n$ podemos hallar cuántas veces va a dividir $n!$, o sea, su exponente.
Fijemos $p_i$ y contabilicemos, por cada una de sus potencias ${p_i}^r$, cuántos múltiplos de ${p_i}^r$ hay entre $1$ y $n$:
- El número de múltiplos de $p_i$ entre $1$ y $n$ es $\lfloor n / p_i \rfloor$.
- El número de múltiplos de ${p_i}^2$ entre $1$ y $n$ es $\lfloor n / {p_i}^2 \rfloor$.
- El número de múltiplos de ${p_i}^3$ entre $1$ y $n$ es $\lfloor n / {p_i}^3 \rfloor$.
- ...
Por lo tanto, el exponente del primo ${p_i}$ es igual a $\lfloor n / p_i \rfloor + \lfloor n / {p_i}^2 \rfloor + \lfloor n / {p_i}^3 \rfloor + \cdots$ (fórmula de Legendre). Aunque es una suma infinita, solo tendremos un número finito de términos que no son cero.

:::info
:information_source: **Ejemplo:** factoricemos $11!$:
Sabemos que $11! = 1 \times 2 \times 3 \times 4 \times 5 \times 6 \times 7 \times 8 \times 9 \times 10 \times 11$, entonces tendremos que precalcular todos los primos menores o iguales a $11$, que son $\{2,3,5,7,11\}$.
- Procesemos el primo $2$:
- Hay $\lfloor 11 / 2 \rfloor = 5$ múltiplos de $2$, que son $\{2,4,6,8,10\}$, por lo tanto, los dividimos todos entre 2 y lo que nos queda por factorizar es $1 \times \color{red}{1} \times 3 \times \color{red}{2} \times 5 \times \color{red}{3} \times 7 \times \color{red}{4} \times 9 \times \color{red}{5} \times 11$.
- Hay $\lfloor 11 / 2^2 \rfloor = 2$ múltiplos de $4$, que son $\{4,8\}$, por lo tanto, los dividimos todos entre 2 y lo que nos queda por factorizar es $1 \times 1 \times 3 \times \color{red}{1} \times 5 \times 3 \times 7 \times \color{red}{2} \times 9 \times 5 \times 11$.
- Hay $\lfloor 11 / 2^3 \rfloor = 1$ múltiplo de $8$, que es $\{8\}$, por lo tanto, los dividimos todos entre 2 y lo que nos queda por factorizar es: $1 \times 1 \times 3 \times 1 \times 5 \times 3 \times 7 \times \color{red}{1} \times 9 \times 5 \times 11$.
- A partir de aquí ya no hay múltiplos de $2^4$, por lo tanto nos detenemos y calculamos el exponente del primo $2$ en la factorización: $5+2+1=8$.
- Procesemos el primo $3$:
- Hay $\lfloor 11 / 3 \rfloor = 3$ múltiplos de $3$, que son $\{3,6,9\}$, por lo tanto, los dividimos todos entre 3 y lo que nos queda por factorizar es $1 \times 1 \times \color{red}{1} \times 1 \times 5 \times \color{red}{1} \times 7 \times 1 \times \color{red}{3} \times 5 \times 11$.
- Hay $\lfloor 11 / 3^2 \rfloor = 1$ múltiplo de $9$, que es $\{9\}$, por lo tanto, los dividimos todos entre 3 y lo que nos queda por factorizar es $1 \times 1 \times 1 \times 1 \times 5 \times 1 \times 7 \times 1 \times \color{red}{1} \times 5 \times 11$.
- A partir de aquí ya no hay múltiplos de $3^3$, por lo tanto el exponente del primo $3$ es igual a $3+1=4$.
- Procesemos el primo $5$:
- Hay $\lfloor 11 / 5 \rfloor = 2$ múltiplos de $5$, que son $\{5,10\}$, por lo tanto, los dividimos todos entre 5 y lo que nos queda por factorizar es $1 \times 1 \times 1 \times 1 \times \color{red}{1} \times 1 \times 7 \times 1 \times 1 \times \color{red}{1} \times 11$.
- A partir de aquí ya no hay múltiplos de $5^2$, por lo tanto el exponente del primo $5$ es igual a $2$.
- Procesemos el primo $7$:
- Hay $\lfloor 11 / 7 \rfloor = 1$ múltiplo de $7$, que es $\{7\}$, por lo tanto, los dividimos todos entre 7 y lo que nos queda por factorizar es $1 \times 1 \times 1 \times 1 \times 1 \times 1 \times \color{red}{1} \times 1 \times 1 \times 1 \times 11$.
- A partir de aquí ya no hay múltiplos de $7^2$, por lo tanto el exponente del primo $7$ es igual a $1$.
- Procesemos el primo $11$:
- Hay $\lfloor 11 / 11 \rfloor = 1$ múltiplo de $11$, que es $\{11\}$, por lo tanto, los dividimos todos entre 11 y lo que nos queda por factorizar es $1 \times 1 \times 1 \times 1 \times 1 \times 1 \times 1 \times 1 \times 1 \times 1 \times \color{red}{1}$.
- A partir de aquí ya no hay múltiplos de $11^2$, por lo tanto el exponente del primo $11$ es igual a $1$.

Ya que terminamos de procesar todos los primos, vemos que no nos faltó nada por factorizar, pues es un producto de puros unos. Por lo tanto, concluímos que $11! = 2^8 \times 3^4 \times 5^2 \times 7 \times 11$.

Una manera alternativa de visualizar esto es:
- $2 = \color{red}{2}$
- $3 = \color{green}{3}$
- $4 = \color{red}{2^2}$
- $5 = \color{purple}{5}$
- $6 = \color{red}{2} \times \color{green}{3}$
- $7 = \color{orange}{7}$
- $8 = \color{red}{2^3}$
- $9 = \color{green}{3^2}$
- $10 = \color{red}{2} \times \color{purple}{5}$
- $11 = 11$

:::

La implementación queda así, separando en una función la fórmula de Legendre:

int legendre(int n, int p){
    // Hallamos el exponente de p en n!
    int sum = 0;
    int term = n / p; // Primer término de la suma
    while(term > 0){  // Iteramos mientras haya algo qué sumar
        sum += term;
        term /= p;    // Usamos la identidad floor(n / p^(i+1)) = floor(floor(n / p^i) / p)
    }
    return sum;
}

// Antes de llamar a esta función, precalculamos los suficientes primos
map<int, int> factoriceFactorial(int n){
    map<int, int> fact;
    for(int p : primes){
        if(p > n) break;
        // Por cada primo p <= n, hallamos su exponente y lo guardamos
        fact[p] = legendre(n, p);
    }
    return fact;
}

La complejidad consiste primero en un precálculo de los primeros $MAX$ primos en $O(MAX \log \log MAX)$, y factorizar $n!$ nos va a costar $O(n / \log n)$, pues por el teorema de los números primos, hay aproximadamente $n / \ln n$ primos menores o iguales a $n$.