---
tags: number-theory, fast-prime-counting, dp, sieve, sublinear
---

# Fast prime counting

Sea $\pi_0(n)$ el número de primos menores o iguales a $n$. Hallar $\pi_0(n)$ de forma eficiente para $n \leq 10^{12}$.

Por el teorema de los números primos, una aproximaxión a $\pi_0(n)$ es $O \left( \dfrac{n}{\ln n} \right)$.

Una forma de hacerlo de forma exacta es usando la criba lineal para hallar todos los primos hasta $n$, y al final devolver el tamaño del arreglo de primos. La complejidad sería $O(n)$, tanto como en tiempo y en memoria.

## Modificación de la criba de Eratostenes
Sea $dp(k, n)$ la cantidad de números que quedan sin tachar en la criba hasta $n$ luego de haber procesado los primeros $k$ primos.

Tenemos el siguiente caso base: $dp(0, n) = n-1$ para toda $n$.

Para obtener la recurrencia de $dp(k, n)$, donde $k \geq 1$, veamos lo siguiente:
- Supongamos que estamos procesando el $k$-ésimo primo, digamos que es $p_k$. Vemos que los números que estaban sin tachar en el paso anterior entre $p_k$ y $\lfloor n / p_k \rfloor$, los podemos multiplicar por $p_k$ y obtener nuevos taches en la criba. Es decir, el número de taches nuevos en la criba será: $dp(k-1, \lfloor n / p_k \rfloor) - dp(k-1, p_k - 1)$.
- Por lo tanto, $dp(k, n) = dp(k-1, n) - [dp(k-1, \lfloor n / p_k \rfloor) - dp(k-1, p_k - 1)]$ para $n \geq p_k^2$, y $dp(k, n) = dp(k-1, n)$ para $n < p_k^2$.
- La respuesta final, es decir, el valor de $\pi_0(n)$ lo hallamos en $dp(\pi_0(\lfloor \sqrt{n} \rfloor), n)$.
- Sea $m = \lfloor \sqrt{n} \rfloor$. Vemos que para calcular $\pi_0(n)$ solo se visitan los estados de la forma $dp(k, x)$, donde $x = 1, 2, \ldots, m, \lfloor n/1 \rfloor, \lfloor n/2 \rfloor, \ldots, \lfloor n/m \rfloor$. Es decir, a lo más visitará $\pi_0(m) \cdot 2m \approx \dfrac{m}{\ln m} 2m \approx \dfrac{4n}{\ln n}$ estados distintos.

Ejemplo para $n=101$:

La implementación de esa idea, optimizando la dp de forma iterativa y ahorrando memoria, queda como:

lli pi_0(lli N){
	int m = sqrt(N);
	vector<lli> lo(m+1), hi(m+1);
	auto at = [&](lli x) -> lli&{
		if(x <= m) return lo[x];
		else return hi[N / x];
	};
	vector<lli> values;
	for(int i = 1; i <= m; ++i){
		values.push_back(i);
		if(N / i != i) values.push_back(N / i);
	}
	sort(values.begin(), values.end(), greater<lli>());
	for(lli n : values){
		at(n) = n - 1;
	}
	for(lli p = 2; p <= m; ++p){
		if(at(p) == at(p - 1)) continue;
		for(lli n : values){
			if(n < p*p) break;
			at(n) = at(n) - (at(n / p) - at(p - 1));
		}
	}
	return at(N);
}

La complejidad en memoria de esta idea es $O(\sqrt{n})$ y en tiempo es $O\left( \dfrac{n^{3/4}}{\ln(n)} \right)$.

## Generalización
Sea $\pi_q(n)$ la suma de las $q$-ésimas potencias de los primos menores o iguales a $n$.

Para hallar $\pi_q(n)$, tenemos que modificar la definición de $dp(k, n)$ para hallar la suma de las $q$-ésimas potencias de los números hasta $n$ que están sin tachar luego de haber procesado los primeros $k$ primos.

- El caso base sería $dp(0, n) =\displaystyle \sum_{i=2}^{n} i^q$, el cual puede ser calculado con una fórmula sencilla para valores pequeños de $q$.
- La recurrencia quedaría como: $dp(k, n) = dp(k-1, n) - p_k^q [dp(k-1, \lfloor n / p_k \rfloor) - dp(k-1, p_k - 1)]$ para $n \geq p_k^2$, y $dp(k, n) = dp(k-1, n)$ para $n < p_k^2$.