Por fin después de mucho batallar ya dimos con la contestación de esta traba que tantos usuarios de esta web han presentado. Si deseas aportar algún detalle no dejes de aportar tu conocimiento.
Solución:
Para $ n $ grandes, su mejor opción es estimar el $ n $ ésimo número primo $ x $, por ejemplo, usando http://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number y luego usar métodos sub-lineales sugeridos por Daniel Fischer y otros para calcular el número exacto $ pi (x) $ de primos menores o iguales a su estimación $ x $ para el $ n $ ésimo primo. Entonces tienes que tomar una decisión. O puede concentrarse en el $ n $ ésimo número primo utilizando la prueba de primalidad para analizar los candidatos a partir de su conjetura inicial, o puede refinar su estimación para el $ n $ ésimo número primo y volver a calcular el número de primos menores o iguales a su estimación de nuevo. Teniendo en cuenta que el error dado para el $ n $ ésimo número primo estimado en el enlace de wikipedia es $ O (n / ( log n) ^ 2) $, y que calcular $ pi (x) $ es aproximadamente $ O ( x ^ 2/3) $ time o mejor, una buena estrategia es esencialmente hacer una especie de búsqueda binaria para refinar su elección de $ x $ de modo que $ pi (x) $ se acerque cada vez más a $ n $ , hasta que el error entre $ pi (x) $ y $ n $, multiplicado por el costo computacional para la prueba de primalidad para números aproximadamente iguales a $ x $, sea menor que el costo computacional de calcular $ pi (x) $ nuevamente . Luego, realiza una prueba de primalidad para concentrarse en el número primo exacto $ n $ ésimo.
Esto se basa principalmente en la buena respuesta de user2566092. En primer lugar, tenga en cuenta que en este momento estamos viendo $ n <10 ^ 22 $ más o menos, probablemente $ n <2 ^ 64 $, ya que, de lo contrario, incluso los métodos de conteo rápido de primos comienzan a tomar mucho tiempo. Dos cosas son importantes para el rendimiento: una buena estimación y un buen método de recuento de primos. Por supuesto, tener un método de conteo rápido para el punto final también es importante, pero menos que los otros dos. No creo que sea necesario hacer más de un recuento primario; si resulta más rápido, creo que eso indica que la estimación o el tamizado deben mejorar.
Para la estimación, la estimación de Cipolla 1902 de segundo orden de Wikipedia no es un mal comienzo, pero es sustancialmente peor que algunos otros métodos. Puede agregar una pequeña corrección de tercer orden a la fórmula de Cipolla que reducirá el error en aproximadamente 1/4 a $ 10 ^ 15 $. Mucho mejor es usar una función R de Riemann inversa, que tiene un error de 3 órdenes de magnitud menor a $ 10 ^ 15 $, con un descuento de solo 11 millones frente a 37 mil millones. Descubrí que lo que funciona mejor para mí es $ rm Li ^ – 1 (n) + rm Li ^ – 1 ( sqrt n) / 4 $, que casi siempre subestima (bueno para tamizar) y se acerca casi tanto como R inversa, mientras que también es un poco más fácil de calcular. Experimente con diferentes estimaciones.
Una vez que hemos encontrado una estimación, realizamos un conteo rápido rápido, por ejemplo, método de Lehmer, OVM o OVM extendido. Este último tiene implementaciones de código abierto capaces de calcular $ 10 ^ 14 $ en un par de segundos y $ 10 ^ 16 $ en medio minuto (los tiempos variarán según la máquina, por supuesto), con muy poco uso de memoria.
Una vez que hemos hecho el conteo de primos, solo necesitamos contar los primos hacia atrás o hacia adelante para compensar el error. Si usamos una buena estimación, el número debería ser bastante pequeño en relación con el número para el que hicimos un recuento primo. En este punto, también debe tenerse en cuenta que existen pruebas rápidas de primalidad determinista para números por debajo de $ 2 ^ 64 $. Ya sea BPSW, una prueba de Miller-Rabin de 7 bases o una prueba de Miller-Rabin con hash de 3 bases será completamente precisa para todos los números de 64 bits. Observé anteriormente que uso una estimación ajustada pero baja, por lo que rara vez tiene que contar hacia atrás; el uso de llamadas repetidas prev_prime funciona bastante bien. Para la búsqueda hacia adelante, que es el caso habitual, hago tamices en segmentos y recuento de los bloques de bits resultantes. Hay varias optimizaciones posibles aquí.
Para darte una idea, parece que nth_prime $ (10 ^ 12) $ tarda 0.8sec, y nth_prime $ (10 ^ 15) $ aproximadamente 1min 2sec en mi computadora, sin usar ninguna tabla. Eso es sustancialmente más rápido que el tamizado de cebos hasta ~ 3.7e16.
Si fuera a contar uno a la vez, un colador sería la mejor opción. Incluso con valores altos utilizando un tamiz tradicional, puede usar el tamiz para reducir segmentos de manera eficiente, por lo que solo unos pocos candidatos deben pasar por una prueba de primalidad. En mi opinión, el Tamiz de Eratóstenes es superior al Tamiz de Atkin, incluso en los raros casos en que este último se implementa correctamente. La segmentación es importante para tamaños grandes. Si solo desea hacer el trabajo en lugar de implementarlo usted mismo, consulte primesieve. Es De Verdad rápido, bien mantenido y con buenas interfaces para C y C ++.
Existe otra alternativa, un enfoque de tabla híbrida. Esto es utilizado por Nth Prime Page, y hace años se habló de ponerlo en SAGE. Aquí, en lugar de utilizar una función de recuento de primos, simplemente almacenamos tablas grandes de recuentos de primos o posiciones primarias n-ésimas, hacemos la búsqueda y luego tamizamos la diferencia. La desventaja es que no escala bien a valores grandes (por ejemplo, la Nth Prime Page está limitada a $ 10 ^ 12 $). Utilizo un método como este para recuentos de primos gemelos, e incluso con solo ~ 100 valores puede guardar un lote de tiempo. Si sus valores no son demasiado grandes y no desea implementar todo el trabajo para un n-ésimo primo calculado rápidamente, esto puede ser algo a considerar. Solo necesita algunas tablas (compiladas o cargadas bajo demanda) y un tamizado rápido de segmentos.
Sección de Reseñas y Valoraciones
Recuerda que puedes compartir este post si te ayudó.