Criba de Gries-Misra

En el manual de la Criba de Eratóstenes, vimos un algoritmo capaz de calcular todos los números primos en el intervalo $[2, N]$ en tiempo $\mathcal{O}(N \log \log N)$. Aquí veremos un algoritmo similar que lo hace en tiempo $\mathcal{O}(N)$, y que además tiene otras aplicaciones. Este algoritmo se debe a Gries y Misra, 1978 y no tiene un nombre consensuado: en fuentes de programación competitiva (1, 2) se le suele llamar “criba en tiempo lineal”.

El algoritmo se basa en el siguiente hecho: todo número compuesto se puede expresar únicamente como $p\cdot q$ donde $q$ es un entero mayor o igual a $2$ y $p$ es un primo menor o igual que cualquier primo que divide a $q$. (Es una consecuencia directa del teorema fundamental de la aritmética, que la descomposición en factores primos de un entero es única). Además, los números primos no se pueden descomponer así. Recordemos en la Criba de Eratóstenes íbamos “marcando” los múltiplos de los primos como compuestos, haciendo que algunos números fueran marcados varias veces: para conseguir que el algoritmo tenga un coste lineal, tenemos que hacer que cada número compuesto se “marque” sólo una vez. Para ello, utilizamos esa descomposición única: cada número compuesto $p\cdot q$ será marcado cuando procesemos el número $q$.

Para hacer eso, inicializamos un vector mindiv donde iremos guardando el mínimo divisor primo de cada número. Al principio inicializamos todos los valores a 0. Vamos iterando para i desde 2 hasta N. En cada iteración, si mindiv[i] es 0, significa que i es primo (no hemos encontrado un q menor que i tal que i=p*q). En caso de que sea primo, ponemos mindiv[i] = i, añadimos i a la lista de primos y para todos los primos p que hemos encontrado hasta ahora (que son menores o iguales que i), “marcamos” i*p, es decir, hacemos la asignación mindiv[i*p] = p. Si mindiv[i] no es igual a 0, entonces también marcamos i*p, pero ahora sólo lo hacemos para valores de p menores o iguales que mindiv[i]. Esto hace que, debido a la factorización única que hemos comentado antes, el valor mindiv[x] sea asignado una única vez para cada x compuesto, y ese valor es en efecto el mínimo factor primo de x.

La implementación es la siguiente:

vector<int> mindiv;
vector<int> primes;

void sieve(int N) {
    mindiv = vector<int>(N+1, 0);
    primes = vector<int>();
    for(int i=2; i <= N; ++i) {
        if(mindiv[i] == 0) {
            mindiv[i] = i;
            primes.push_back(i);
        }
        for(int j=0; j < primes.size() and primes[j] <= mindiv[i] and primes[j]*i <= N; ++j) {
            mindiv[i*primes[j]] = primes[j];
        }
    }
}

Para calcular los números primos entre $2$ y $N$ no suele merecer la pena implementar esta criba en lugar de la de Eratóstenes, ya que a nivel temporal no hay mucha diferencia (aunque esta sea $\mathcal{O}(N)$ y la de Eratóstenes $\mathcal{O}(N \log \log N)$, esta suele tener un mayor factor constante) y la criba de Gries-Misra requiere más memoria al almacenar un vector de enteros en lugar del vector de booleanos que se almacena en la de Eratóstenes. Sin embargo, esta criba nos proporciona más información que la de Eratóstenes. A través del vector mindiv podemos calcular muy rápidamente la descomposición en factores primos de cualquier número en el intervalo $[2, N]$ (simplemente vamos obteniendo los primos uno por uno, dividiendo el número cada vez por su mínimo factor primo). La criba también se puede extender para computar valores de funciones aritméticas multiplicativas (suma de divisores, phi de Euler, etcétera) en el intervalo $[2, N]$: en esta entrada de CodeForces se explica esta aplicación.