Que $\pi(x)$ sea el número de números primos no mayor al $x$.
Artículo de Wikipedia dice que $\pi(10^{23}) = 1,925,320,391,606,803,968,923$.
¿La pregunta es cómo calcular $\pi(x)$ % grande $x$en un tiempo razonable? ¿Qué algoritmos existen para eso?
Respuestas
¿Demasiados anuncios?
El primer más eficiente algoritmos de conteo actualmente conocidos son todos esencialmente optimizaciones del método desarrollado por Meissel en 1870, por ejemplo, ver la discusión aquí http://primes.utm.edu/howmany.shtml
schmidty
Puntos
703
La Criba de Atkin es uno de lo más rápido algoritmo utilizado para calcular $pi(x)$. La página de Wikipedia dice que su complejidad es O (N/log log N).
(editar)
Encontré un proyecto de computación distribuida que era capaz de calcular $pi(4\times 10^{22})$, tal vez podría ser útil.
