Criba lineal

Dado un número $n$ , encontrar todos los números primos en un segmento $[2;n]$ .

La forma estándar de resolver esta tarea es usar la criba de Eratóstenes. Este algoritmo es muy simple, pero tiene tiempo de ejecución $O(n \log \log n)$ .

Aunque hay muchos algoritmos conocidos con tiempo de ejecución sublineal (es decir, $o(n)$ ), el algoritmo que se describe abajo resulta interesante por su simplicidad: no es más complejo que la criba clásica de Eratóstenes.

Además, el algoritmo dado acá calcula las factorizaciones de todos los números del segmento $[2; n]$ como efecto colateral, y eso puede ser útil en muchas aplicaciones prácticas.

La debilidad del algoritmo dado es que usa más memoria que la criba clásica de Eratóstenes: requiere un arreglo de $n$ números, mientras que para la criba clásica de Eratóstenes basta con $n$ bits de memoria (lo que es 32 veces menos).

Así, tiene sentido usar el algoritmo descrito solo para números del orden de $10^7$ y no mayores.

El algoritmo se debe a Paul Pritchard. Es una variante del Algoritmo 3.3 en (Pritchard, 1987: véanse las referencias al final del artículo).

Algoritmo

Nuestro objetivo es calcular el menor factor primo $lp [i]$ de cada número $i$ en el segmento $[2; n]$ .

Además, necesitamos guardar la lista de todos los números primos encontrados: llamémosla $pr []$ .

Inicializaremos los valores $lp [i]$ con ceros, lo que significa que asumimos que todos los números son primos. Durante la ejecución del algoritmo este arreglo se irá llenando de a poco.

Ahora recorreremos los números de 2 a $n$ . Tenemos dos casos para el número actual $i$ :

$lp[i] = 0$ — eso significa que $i$ es primo, es decir, no hemos encontrado ningún factor más pequeño para él.
Por lo tanto, asignamos $lp [i] = i$ y agregamos $i$ al final de la lista $pr[]$ .
$lp[i] \neq 0$ — eso significa que $i$ es compuesto, y su menor factor primo es $lp [i]$ .

En ambos casos actualizamos los valores de $lp []$ para los números que son divisibles por $i$ . Sin embargo, nuestro objetivo es aprender a hacerlo de forma tal que se asigne un valor $lp []$ a lo sumo una vez para cada número. Podemos hacerlo de la siguiente manera:

Consideremos los números $x_j = i \cdot p_j$ , donde $p_j$ son todos los números primos menores o iguales que $lp [i]$ (por eso necesitamos guardar la lista de todos los números primos).

Asignaremos un nuevo valor $lp [x_j] = p_j$ para todos los números de esta forma.

La demostración de corrección de este algoritmo y su tiempo de ejecución se pueden encontrar después de la implementación.

Implementación


const int N = 10000000;
vector<int> lp(N+1);
vector<int> pr;
 
for (int i=2; i <= N; ++i) {
	if (lp[i] == 0) {
		lp[i] = i;
		pr.push_back(i);
	}
	for (int j = 0; i * pr[j] <= N; ++j) {
		lp[i * pr[j]] = pr[j];
		if (pr[j] == lp[i]) {
			break;
		}
	}
}

Demostración de corrección

Hay que demostrar que el algoritmo asigna todos los valores $lp []$ de forma correcta, y que cada valor se asignará exactamente una vez. Por lo tanto, el algoritmo tendrá tiempo de ejecución lineal, ya que el resto de las acciones del algoritmo, obviamente, trabajan en $O (n)$ .

Nótese que cada número $i$ tiene exactamente una representación de la forma:

$i = lp [i] \cdot x,$

donde $lp [i]$ es el menor factor primo de $i$ , y el número $x$ no tiene ningún factor primo menor que $lp [i]$ , es decir

$lp [i] \le lp [x].$

Ahora comparemos esto con las acciones de nuestro algoritmo: de hecho, para cada $x$ recorre todos los números primos por los que se podría multiplicar, es decir, todos los números primos hasta $lp [x]$ inclusive, para obtener los números de la forma dada arriba.

Por lo tanto, el algoritmo recorrerá cada número compuesto exactamente una vez, asignando allí los valores correctos de $lp []$ . Q.E.D.

Tiempo de ejecución y memoria

Aunque el tiempo de ejecución $O(n)$ es mejor que el $O(n \log \log n)$ de la criba clásica de Eratóstenes, la diferencia entre ellos no es tan grande. En la práctica la criba lineal (linear sieve) se ejecuta aproximadamente tan rápido como una implementación típica de la criba de Eratóstenes.

En comparación con versiones optimizadas de la criba de Eratóstenes, p. ej. la criba segmentada, es mucho más lenta.

Considerando los requisitos de memoria de este algoritmo — un arreglo $lp []$ de longitud $n$ , y un arreglo $pr []$ de longitud $\frac n {\ln n}$ —, este algoritmo parece ser peor que la criba clásica en todos los aspectos.

Sin embargo, su cualidad redentora es que este algoritmo calcula un arreglo $lp []$ , que nos permite encontrar la factorización de cualquier número del segmento $[2; n]$ en un tiempo del orden del tamaño de esa factorización. Además, usando solo un arreglo extra podremos evitar divisiones al buscar la factorización.

Conocer las factorizaciones de todos los números es muy útil para algunas tareas, y este algoritmo es uno de los pocos que permiten encontrarlas en tiempo lineal.

Referencias

Paul Pritchard, Linear Prime-Number Sieves: a Family Tree, Science of Computer Programming, vol. 9 (1987), pp.17-35.