Recuento de números primos: ¿alternativas rápidas al método combinatorio de Lagarias-Miller-Odlyzko o a los métodos analíticos de Lagarias-Odlyzko?

Question

Supongo que la pregunta lo dice todo: estoy intentando localizar algoritmos rápidos para el recuento de primas para saber qué hay.

Ya conozco los dos algoritmos mencionados en el título (esencialmente las secciones 3.6.1 y 3.6.2 de mi copia de 2001 de Crandall & Pomerance's Prime Numbers: A Computational Perspective de Crandall y Pomerance, aunque al mirar en Internet, parece que podrían ser las secciones 3.7.1 y 3.7.2 de una adición más reciente).

¿Existe alguna otra familia de algoritmos en el rango de, digamos, O(n^2/3 + epsilon) de tiempo y O(n^1/2+epsilon) de espacio o mejor para el conteo de primos? Y si es así, ¿dónde podría encontrarlos? ¿Hay algún buen repositorio de varios algoritmos de conteo de primos en algún lugar de la web?

Answer 1

No sé si esto puede interesarte, pero hay una bonita fórmula debida a Lifchitz que permite calcular la paridad de $\pi(x)$ en $O(\sqrt{x}\log x)$ : si $\Pi(x)$ representan el número de potencias primos hasta $x$ entonces
$$ \Pi(x) \equiv \sum_{m\leq \sqrt{x}} \mu(m) \sum_{n\leq \sqrt(x/m^2)} \left\lfloor\frac{x}{nm^2}\right\rfloor \pmod{2} $$ Esto es más bien un comentario, pero no puedo comentar porque no tengo suficiente reputación .

Answer 2

Creo que http://primes.utm.edu/howmany.shtml está bastante actualizado.

Answer 3

Aquí hay un resumen de un montón de diferentes algoritmos para contar y enumerar primos con un montón de enlaces a una discusión más profunda

http://www.mail-archive.com/sage-devel@googlegroups.com/msg44646.html