Criba de Eratóstenes

Queremos ver cuáles de los números en el rango $[1, N]$ son primos. Un algoritmo bastante eficiente para resolver este problema es la Criba de Eratóstenes, llamada así por su inventor, Eratóstenes de Cirene, que vivió alrededor del 200 a. C.

El algoritmo es el siguiente: se disponen los números del $2$ al $N$ en una tabla. Primero se marcan todos los múltiplos de $2$ y se añade el $2$ a la lista de primos. Después se marcan todos los múltiplos de $3$ y se añade el $3$ a la lista de primos. Después se mira el $4$, se ve que está marcado y eso significa que es divisible por $2$, por lo que no es primo. Después se llega al $5$, que al no estar marcado es primo, se marcan todos sus múltiplos y se añade a la lista de primos. Así, se va progresando por la tabla: cuando se llega a un número que no está marcado, sabemos que es primo (porque no es divisible por ningún primo menor), se marcan todos sus múltiplos y se añade a la lista de primos. Aquí hay una animación del algoritmo.

La implementación del algoritmo sería la siguiente:

vector<bool> isPrime;
vector<int> primes;
void criba(int n) {
    isPrime = vector<bool>(n, true);
    primes = vector<int>();
    isPrime[0] = isPrime[1] = false;
    for (int i=2; i<n; ++i) {
        if (isPrime[i]) {
            primes.push_back(i);
            for (int h=2; h*i<n; ++h) isPrime[i*h] = 0;
        }
    }
}

def criba(n):
	primes = []
	isPrime = [1 for i in range(n)]
	isPrime[0] = isPrime[1] = 0

	for i in range(n):
		if isPrime[i]:
			primes.append(i)
			h = 2
			while i*h < n:
				isPrime[i*h] = 0
				h += 1

	return primes, isPrime

Después de llamar a sieve(N), el vector primes contiene la lista de primos menores o iguales a N, mientras que isPrime[n] contiene si n es primo. 

Por cada primo $p$, el bucle interior hace unas $\frac{N}{p}$ iteraciones, así que el número total de iteraciones es $\frac{N}{2} + \frac{N}{3} + \frac{N}{5} + \ldots $. Es un resultado matemático que la suma de inversos de los primos menores o iguales a $N$ crece como $\log \log N$, así que la complejidad del algoritmo es de $\mathcal{O}(N \log \log N)$. 

Ejercicio: En la animación sólo empieza a marcar los múltiplos de $p$ a partir de $p^2$, no de $2p$. ¿Por qué se puede hacer esto?