---
tags: number-theory, sieve-of-eratosthenes, prime-numbers, sieve, divisors-sieve, lowest-prime, greatest-prime
---

# Criba de Eratóstenes
Este es uno de los algoritmos más clásicos y a la vez eficientes que se relacionan con los números primos. Su objetivo es el siguiente: obtener todos los números primos entre $1$ y $n$.

## Motivación
Una forma sencilla de obtenerlos es reusar el test primalidad que vimos antes para cada número en el rango $[1, n]$, e ir guardando todos los números que resulten primos:

### Algoritmo 1

vector<int> getPrimes(int n){
    vector<int> primes;
    for(int i = 1; i <= n; i++){
        if(isPrime(i)){
            primes.push_back(i);
        }
    }
    return primes;
}

Si usamos el test de primalidad optimizado, la complejidad es aproximadamente $O(\sqrt{1} + \sqrt{2} + \cdots + \sqrt{n}) = O(n \sqrt{n})$, la cual es aceptable para $n \leq 10^5$. Veámos cómo mejorar esta complejidad.

## Criba básica
La idea principal de la criba de Eratóstenes es tener un arreglo de tamaño $n$ tal que la posición $i$ nos diga si $i$ es primo o no. Al principio marcaremos todos los números como primos, excepto al $1$.

- Comenzando con el $2$, que es el primer primo, iremos tachando todos sus múltiplos mayores en el arreglo ($4, 6, 8, 10, \ldots$), pues sabemos que ninguno de ellos será primo, ya que el $2$ los divide a todos ellos.
- Luego seguimos con el $3$, que es el siguiente primo, y haremos lo mismo, tachar todos sus múltiplos mayores ($6, 9, 12, 15, \ldots$) como números compuestos.
- Al momento de seguir con el $4$ podríamos tachar todos sus múltiplos ($8, 12, 16, \ldots$), pero sorpresa, todos ellos ya fueron tachados por el $2$, entonces no tiene sentido volverlos a tachar.
- Siguiendo con el $5$ vemos que no ha sido tachado por nadie hasta ahora, entonces también tiene que ser primo, y tachamos todos sus múltiplos mayores ($10, 15, 20, 25, \ldots$).
- Seguimos avanzando y cada que encontremos un número sin tachar, marcamos todos sus múltiplos mayores.

Por lo tanto, tenemos la siguiente propiedad: un número $n$ es primo si no es divisible entre los primos $p$ tales que $p < n$. Este es un resultado más fuerte que el que usamos en el test de primalidad básico: verificábamos que $n$ no fuera divisible por ningún número en el rango $[2, n-1]$, ahora podemos verificar únicamente con los primos en ese rango, y esa es la idea sobre la que descansa la correctitud de la criba, ya que si llegamos a la $i$-ésima posición y nadie la ha tachado, es porque no hubo primos menores a $i$ que lo dividieran, por lo tanto $i$ tiene que ser primo.

De esta forma, todos los números que queden sin tachar en el arreglo al final del algoritmo son primos, y todos los tachados son compuestos.

:::info
:information_source: **Ejemplo:** veamos cómo se ven las iteraciones del algoritmo, suponiendo que queremos obtener los primos entre $1$ y $20$:

Al principio nuestro arreglo de marquitas se ve así, todos los números son primos excepto el 1:
$$
\require{cancel}
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
\cancel{1} & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\
\hline
\end{array}
$$

Vemos que el $2$ es el primer número sin marcar, por lo tanto marcamos todos sus múltiplos mayores:
$$
\require{cancel}
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
\cancel{1} & 2 & 3 & \cancel{4} & 5 & \cancel{6} & 7 & \cancel{8} & 9 & \cancel{10} & 11 & \cancel{12} & 13 & \cancel{14} & 15 & \cancel{16} & 17 & \cancel{18} & 19 & \cancel{20} \\
\hline
\end{array}
$$

El $3$ sigue, por lo tanto:
$$
\require{cancel}
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
\cancel{1} & 2 & 3 & \cancel{4} & 5 & \cancel{6} & 7 & \cancel{8} & \cancel{9} & \cancel{10} & 11 & \cancel{12} & 13 & \cancel{14} & \cancel{15} & \cancel{16} & 17 & \cancel{18} & 19 & \cancel{20} \\
\hline
\end{array}
$$

Sigue el $4$, pero como está tachado sabemos que no es primo, por lo tanto no vale la pena tachar sus múltiplos mayores.

Sigue el $5$, y como no está marcado, es primo y podemos tachar todos sus múltiplos. Sin embargo, no obtendremos nuevos taches, y podemos deternos hasta aquí. Se puede demostrar también que con ningún otro número obtendremos nuevos taches, entonces podemos parar aquí.

Finalmente, los números sin tachar son: $\{2, 3, 5, 7, 11, 13, 17, 19\}$, que son exactamente los primos menores o iguales a $20$.
:::

Una primera implementación de esta idea queda como:

### Algoritmo 2: criba de Eratóstenes básica

vector<bool> sieve(int n){
    vector<bool> is(n+1, true); // arreglo de marcas inicializado en true, es decir, todos los números son "primos" al inicio
    is[0] = is[1] = false;      // excepto el 0 y el 1
    for(int i = 2; i <= n; i++){
        if(is[i]){ // si el número actual es primo, marcamos todos sus múltiplos mayores
            for(int j = 2*i; j <= n; j += i){ // el primer múltiplo mayor a i es 2*i, y damos saltos de i en i
                is[j] = false;
            }
        }
    }
    return is;
}

La complejidad de esta implementación es $\displaystyle O(n/2+n/3+n/5+\cdots) = O\left( n \sum_{\substack{p \leq n \\ p \text{ primo}}} \frac{1}{p} \right) = O(n \log \log n)$, es decir, una mejora considerable respecto a $O(n \sqrt{n})$, lo que la hace viable para $n \leq 10^7$. Pero ahora, tenemos una complejidad en memoria de $O(n)$.

Sin embargo, podemos optimizarla aún más. En el ejemplo anterior vimos que llegamos a un punto en donde no obtuvimos más marcas, ¿cuál es dicho punto? Supongamos que estamos procesando el primo $i$, entonces todos sus múltiplos mayores son de la forma $k*i$ para $k \geq 2$. Sea $j = k*i$, entonces para que $j$ sea tachado por ++primera vez++ por el primo $i$, necesitamos que $i$ sea el *divisor primo más pequeño* de $j$, es decir, si $(i, k)$ fuera una pareja de divisores de $j$, entonces $i \leq k$, lo que implica que $i^2 \leq j$, o $j \geq i^2$. Por lo tanto, cambiamos el `j = 2*i` de la línea 6 por `j = i*i`, y así reduciremos el número de taches duplicados.

:::info
:information_source: **Ejemplo:**
- Si estamos procesando el primo $2$, todos los números que tacharemos comenzarán en $2^2=4$, es decir, tachamos $4, 6, 8, 10, \ldots$
- Si estamos procesando el primo $3$, comenzamos a tachar desde $3^2=9$, tachando así $9, 12, 15, 18, \ldots$
- Si estamos procesando el primo $5$, comenzamos a tachar desde $5^2=25$, tachando así $25, 30, 35, 40, \ldots$
- Si estamos procesando el primo $7$, comenzamos a tachar desde $7^2=49$, tachando así $49, 56, 63, 70, \ldots$
:::

Pero como $j \leq n$, entonces también se cumple que $i^2 \leq n$, por lo tanto también hay que cambiar la línea 4 la parte de `i <= n` por `i*i <= n`. Es por eso que en el ejemplo a partir del 5 ya no hubo más taches, pues teníamos que $n=20$, entonces $4^2 \leq 16$ pero $5^2 > 20$.

Aún con estos cambios, la complejidad sigue siendo $O(n \log \log n)$, pero con una constante más pequeña, haciéndola viable incluso para $n \leq 10^8$.

Una optimización más que podemos hacer es similar a la que hicimos con los números pares en el test de primalidad: podemos marcar todos los múltiplos mayores de $2$ como compuestos desde el principio, y cada que tachemos números, solo iteramos por sus múltiplos impares. La implementación quedaría así, ya tomando en cuenta todas las optimizaciones:

### Algoritmo 3: criba de Eratóstenes básica optimizada

vector<bool> sieve(int n){
    vector<bool> is(n+1, true); // arreglo de marcas inicializado en true, es decir, todos los números son "primos" al inicio
    is[0] = is[1] = false;      // excepto el 0 y el 1
    for(int i = 4; i <= n; i += 2){
        is[i] = false; // marcamos todos los múltiplos mayores de 2 como compuestos
    }
    for(int i = 3; i*i <= n; i += 2){ // comenzamos a iterar por los impares desde el 3
        if(is[i]){ // si el número actual es primo, marcamos todos sus múltiplos mayores
            for(int j = i*i; j <= n; j += 2*i){ // comenzamos en i*i y solo iteramos por los impares
                is[j] = false;
            }
        }
    }
    return is;
}

## Obtener el arreglo de primos a través de la criba
Hasta ahorita solo vimos cómo obtener el arreglo si nos dice si un número es primo o no, pero no obtuvimos el arreglo de primos como tal. Para obtenerlo hay dos maneras:
- Ya que tenemos el arreglo de marcas, iteramos por todas las posiciones y guardamos en un arreglo todos los números que sí son primos.

### Algoritmo 4: obtener primos a través de la criba

vector<int> getPrimes(int n){
    vector<bool> is = sieve(n);
    vector<int> primes;
    for(int i = 1; i <= n; i++){
        if(is[i]){
            primes.push_back(i);
        }
    }
    return primes;
}

- Otra forma es obtenerlos al mismo tiempo que tachamos los números. Del algoritmo 3 cada que detectemos un primo en la línea 8, simplemente lo guardamos en el arreglo de primos. Solo que ahora habría que cambiar el límite del `for` de la línea 7 a `i <= n` para guardar todos los primos, y verificar que `j = i*i` de la línea 9 no se vaya a desbordar:

### Algoritmo 5: obtener primos al mismo tiempo

vector<int> getPrimes(int n){
    vector<bool> is(n+1, true);
    vector<int> primes = {2}; // introducimos el 2 a mano, pues solo procesamos los primos impares por la optimización
    is[0] = is[1] = false;
    for(int i = 4; i <= n; i += 2){
        is[i] = false;
    }
    for(int i = 3; i <= n; i += 2){
        if(is[i]){
            primes.push_back(i);     // como i es primo, lo introducimos al arreglo
            if((long long)i*i <= n){ // chequeo adicional para evitar desbordar i*i
                for(int j = i*i; j <= n; j += 2*i){
                    is[j] = false;
                }
            }
        }
    }
    return primes; // ahora devolvemos el arreglo de primos
}

## Criba de divisores
Ahora tenemos el siguiente problema: hallar el número de divisores para cada número en el rango $[1, n]$. Una forma de hacerlo es usar el método `getDivisors()` de la sección pasada para cada número, obteniendo una complejidad de $O(n \sqrt{n})$.

Pero podemos usar una idea similar a la criba de primos: para cada $i$ en el rango $[1, n]$ vamos a sumarle 1 a cada múltiplo de $i$ que no exceda $n$, esta vez comenzando desde $i$.

:::info
:information_source: **Ejemplo:** si queremos saber cuántos divisores tiene cada número entre $1$ y $7$, realizamos los siguientes pasos:
- Al principio tenemos el arreglo inicializado en ceros:
$$
\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
n & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
\hline
divs[n] & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
\hline
\end{array}
$$
- Le sumamos 1 a todos los múltiplos de $1$: $1, 2, 3, 4, 5, 6, 7$:
$$
\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
n & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
\hline
divs[n] & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
\hline
\end{array}
$$
- Le sumamos 1 a todos los múltiplos de $2$: $2, 4, 6$:
$$
\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
n & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
\hline
divs[n] & 1 & 2 & 1 & 2 & 1 & 2 & 1 \\
\hline
\end{array}
$$
- Le sumamos 1 a todos los múltiplos de $3$: $3, 6$:
$$
\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
n & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
\hline
divs[n] & 1 & 2 & 2 & 2 & 1 & 3 & 1 \\
\hline
\end{array}
$$
- A partir del $4$ solo habrá un múltiplo dentro del rango, por lo tanto, le sumamos 1 al $4, 5, 6, 7$:
$$
\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
n & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
\hline
divs[n] & 1 & 2 & 2 & 3 & 2 & 4 & 2 \\
\hline
\end{array}
$$
:::

Esto funciona, pues podemos representar a los múltiplos de $i$ como $i*j$. Sea $i_j=i*j$, entonces $i | i_j$, y en cada paso le estamos sumando 1 al número de divisores de $i_j$, que es justamente el divisor $i$.

La implementación de esta idea es muy sencilla:

### Algoritmo 6: criba de número de divisores

vector<int> divsSieve(int n){
    vector<int> divs(n+1); // incializamos el arreglo en ceros
    for(int i = 1; i <= n; i++){
        for(int j = i; j <= n; j += i){ // iteramos por todos los múltiplos de i
            divs[j]++;
        }
    }
    return divs;
}

Y la complejidad queda como $O(n+n/2+n/3+n/4+\cdots) = O(n(1+1/2+1/3+1/4+\cdots)) = O(n \log n)$.

Podemos modificar esta criba para obtener la suma de divisores en lugar del número de divisores, simplemente cambiando la línea 5 a `divs[j] += i`, o incluso obtener los divisores como tal para cada número en el rango, solo habría que cambiar la línea por `divs[j].push_back(i)` y que `divs` sea ahora un arreglo de arreglos.

## Algunas observaciones
La criba de Eratóstenes también sirve como test de primalidad, pues una vez obtenido el arreglo, contestar las queries sobre si un número es primo o no son en $O(1)$. Sin embargo, hay que tomar en cuenta que esta criba tiene una complejidad lineal en memoria, por lo que si queremos saber si un número alrededor de $10^{14}$ es primo, este método no nos sirve. Aquí lo correcto es usar el test de primalidad optimizado que vimos en la sección anterior. Por lo tanto:
- Si tenemos muchas queries pero con valores alrededor de $10^8$, usamos esta criba con un precálculo de $O(MAX \log \log MAX)$ y con una complejidad de $O(1)$ para cada query.
- Si tenemos pocas queries pero con valores más grandes, no hacemos precálculo y contestamos cada una de ellas en $O(\sqrt{n})$.

Para el problema del número o suma de divisores, aplica el mismo razonamiento.

También podemos optimizar el test de primalidad que corre en $O(\sqrt{n})$ combinándolo con la criba de Eratóstenes:
- Usamos la criba para precalcular los primos hasta $\lfloor \sqrt{MAX} \rfloor$.
- En el método `isPrime()` (algoritmo 5 de la sección anterior), en lugar de iterar por todas las $d$'s en la línea 3, iteramos directamente sobre todos los primos $p$ obtenidos tales que $p^2 \leq n$. Esto permite reducir un poco la complejidad a $O(\sqrt{n}/\log(n))$, y la implementación queda como:

### Algoritmo 7: test de primalidad combinado con la criba

// precalcular solo una vez el arreglo primes con la criba antes de llamar a esta función
bool isPrime(int n){
    if(n == 1) return false; // El 1 sigue siendo un caso especial
    for(int p : primes){ // Ahora iteramos únicamente sobre los primos
        if((long long)p*p > n) break; // Solo nos interesan los primos p tales que p*p <= n
        if(n % p == 0){
            return false; // Encontramos un divisor primo de n que no es ni 1 ni n
        }
    }
    return true; // Si llegamos hasta este punto, n tiene que ser primo
}

## Criba del factor primo más pequeño
Ahora queremos obtener por cada número en el rango $[1,n]$ su factor primo más pequeño. Es decir, el número primo más pequeño en la lista de divisores de $i$, para toda $i \in [1,n]$.

:::info
:information_source: **Ejemplo:** sea $lp[n]$ el factor primo más pequeño de $n$. Entonces:
- $lp[2] = 2$
- $lp[3] = 3$
- $lp[4] = 2$
- $lp[5] = 5$
- $lp[6] = 2$
- $lp[7] = 7$
- $lp[8] = 2$
- $lp[9] = 3$
- $lp[10] = 2$
:::

Algunas propiedades de $lp[n]$ son:
- Si $n$ es par, entonces $lp[n] = 2$.
- Si $n$ es primo, entonces $lp[n] = n$.
- Si $n$ es compuesto, entonces $lp[n]^2 \leq n$.
- $lp[1]$ no está definido.

Para hallar el arreglo $lp[]$, tenemos que realizar una modificación a la criba original: en lugar de guardar el arreglo de marcas $is[]$, lo vamos a reemplazar con el arreglo de enteros $lp[]$, y al principio tendremos que $lp[i]=i$ para toda $i \in [1,n]$. Los cambios son los siguientes:
- En la línea 8, para saber si el número actual $i$ es primo, haremos el chequeo: `if(lp[i] == i)`.
- En la línea 13, ahora poner una marca de número compuesto implica actualizar el factor primo más pequeño: `lp[j] = min(lp[j], i)`.
- Al principio hacemos que $lp[i]=2$ para toda $i$ par, en caso de que decidamos utilizar esta optimización.

:::info
:information_source: **Ejemplo:** veamos una simulación de estas modificaciones para hallar $lp[]$ de $1$ a $20$ (sin la optimización de números pares):

Al principio nuestro arreglo se inicializa así (el valor de $lp[1]$ puede valer lo que sea):
$$
\require{cancel}
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\
\hline
lp[n] & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\
\hline
\end{array}
$$

Tenemos que $lp[2]=2$, por lo tanto $2$ es primo y actualizamos todos sus múltiplos mayores:
$$
\require{cancel}
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\
\hline
lp[n] & 1 & 2 & 3 & \color{red}{2} & 5 & \color{red}{2} & 7 & \color{red}{2} & 9 & \color{red}{2} & 11 & \color{red}{2} & 13 & \color{red}{2} & 15 & \color{red}{2} & 17 & \color{red}{2} & 19 & \color{red}{2} \\
\hline
\end{array}
$$

Tenemos que $lp[3]=3$, por lo tanto $3$ es primo y actualizamos todos sus múltiplos mayores:
$$
\require{cancel}
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\
\hline
lp[n] & 1 & 2 & 3 & 2 & 5 & 2 & 7 & 2 & \color{red}{3} & 2 & 11 & 2 & 13 & 2 & \color{red}{3} & 2 & 17 & 2 & 19 & 2 \\
\hline
\end{array}
$$

Tenemos que $lp[4] \neq 4$, por lo tanto $4$ no es primo.

Comno $5^2 > 20$, terminamos el algoritmo y el arreglo $lp[]$ queda como la última iteración.

:::

Tener precalculados estos primos más pequeños nos será de mucha ayuda para un algoritmo de factorización de la siguiente sección.

Modificando el algoritmo 3, la implementación queda como:
### Algoritmo 8: criba del factor primo más pequeño

vector<int> lpSieve(int n){
    vector<int> lp(n+1);           // arreglo del factor primo más pequeño
    iota(lp.begin(), lp.end(), 0); // usamos la STL para rellenar el arreglo inicial
    for(int i = 4; i <= n; i += 2){
        lp[i] = 2; // 2 es el factor primo más pequeño de todos los números pares
    }
    for(int i = 3; i*i <= n; i += 2){ // comenzamos a iterar por los impares desde el 3
        if(lp[i] == i){ // si el número actual es primo, actualizamos todos sus múltiplos mayores
            for(int j = i*i; j <= n; j += 2*i){ // comenzamos en i*i y solo iteramos por los impares
                lp[j] = min(lp[j], i);
            }
        }
    }
    return lp;
}

## Criba del factor primo más grande
Ahora hallaremos el arreglo $gp[]$, donde $gp[i]$ nos dice el divisor primo más grande de $i$.

:::info
:information_source: **Ejemplo:** Tenemos los siguientes valores para el arreglo $gp[]$:
- $gp[2] = 2$
- $gp[3] = 3$
- $gp[4] = 2$
- $gp[5] = 5$
- $gp[6] = 3$
- $gp[7] = 7$
- $gp[8] = 2$
- $gp[9] = 3$
- $gp[10] = 5$
:::

A diferencia del factor primo más pequeño, el factor primo más grande solo cumple que si $n$ es primo, entonces $gp[n] = n$. Por lo tanto, podemos seguir usando la condición `if(gp[i] == i)` para verificar si $i$ es primo, pero ya no podemos usar la optimización de `i*i <= n`, pues ahora no siempre tendremos que $gp[n]^2 \leq n$, ni la de los números pares. Las actualizaciones ahora las haremos con `gp[j] = i`, pues como iteramos por todas las $i$'s en orden, siempre iremos guardando el primo más grande que divide a $j$.

La implementación queda como:

### Algoritmo 9: criba del factor primo más grande

vector<int> gpSieve(int n){
    vector<int> gp(n+1);           // arreglo del factor primo más grande
    iota(gp.begin(), gp.end(), 0); // usamos la STL para rellenar el arreglo inicial
    for(int i = 2; i <= n; i++){
        if(gp[i] == i){ // si el número actual es primo, actualizamos todos sus múltiplos mayores
            for(int j = 2*i; j <= n; j += i){
                gp[j] = i; // al siempre actualizar los múltiplos, garantizamos siempre guardar el factor primo más grande
            }
        }
    }
    return gp;
}

## Criba segmentada

## Hallar primos en un rango