límites más estrechos:
static const unsigned short primes_small[] = {0,2,3,5,7,11};
static unsigned long nth_prime_upper(unsigned long n) {
double fn = (double) n;
double flogn, flog2n, upper;
if (n < 6) return primes_small[n];
flogn = log(n);
flog2n = log(flogn);
if (n >= 688383) /* Dusart 2010 page 2 */
upper = fn * (flogn + flog2n - 1.0 + ((flog2n-2.00)/flogn));
else if (n >= 178974) /* Dusart 2010 page 7 */
upper = fn * (flogn + flog2n - 1.0 + ((flog2n-1.95)/flogn));
else if (n >= 39017) /* Dusart 1999 page 14 */
upper = fn * (flogn + flog2n - 0.9484);
else /* Modified from Robin 1983 for 6-39016 _only_ */
upper = fn * (flogn + 0.6000 * flog2n);
if (upper >= (double) ULONG_MAX) {
/* Adjust this as needed for your type and exception method */
if (n <= 425656284035217743UL) return 18446744073709551557UL;
fprintf(stderr, "nth_prime_upper overflow\n"; exit(-1);
}
return (unsigned long) ceil(upper);
}
Estos no deben nunca ser inferior a la nth_prime real, debería funcionar para cualquier entrada de 64 bits, y ser de un orden de magnitud o más cerca que la fórmula de Robin dado anteriormente (o la fórmula complicada de rango limitado de Wimblik). Para mi uso, tengo una tabla de primos pequeños un poco más grande, así que puedo ajustar un poco más la última estimación. Técnicamente, a partir de las fórmulas podríamos usar floor() en lugar de ceil() pero me preocupa la precisión.
Editar: Otra opción para mejorar esto un poco es implementar buenos límites de recuento de primos (por ejemplo, Axler 2014) y hacer una búsqueda binaria en ellos. Mi código para este método tarda ~ 10 veces más que lo anterior (aún se ejecuta en menos de un milisegundo), pero puede reducir el porcentaje de error en un orden de magnitud.
Si desea una estimación para el primer enésima, que puede hacer:
- Cipolla 1902 (ver Dusart 1999 la página 12 o this paper encuentro tres términos (m = 2), además de un factor de corrección de tercer orden a. ser útil, pero con más términos oscila demasiado.La fórmula que se muestra en el enlace de Wikipedia es esta fórmula (con m = 2) .Utilizar los dos términos inversa li o inversa Riemann R a continuación dará mejores resultados.
- Calcular los límites superiores e inferiores de Dusart 2010 y el promedio de los resultados. No está mal, aunque sospecho que usar un promedio ponderado funcionará mejor ya que los límites no son igualmente ajustados.
- li^{- 1} (n) Dado que li (n) es una aproximación decente al recuento de primos, el inverso es una aproximación decente nth_prime. Esto, y todo lo demás, se puede hacer bastante rápido como una búsqueda binaria en la función.
- li^{- 1} (n) + li^{- 1} (sqrt (n))/4 Más cerca, ya que se está acercando a R (n)
- R^{- 1} Lo inverso La función R de Riemann es la aproximación promedio más cercana que sé que es razonable.
Por último, si tiene un método de recuento de primos muy rápido, como una de las implementaciones de LMO (ahora hay tres implementaciones de código abierto), puede escribir un método nth_prime preciso rápido. La computación de la 10 ° 10 primo se puede hacer en unos pocos milisegundos, y la 10^13 en un par de segundos (en una máquina rápida moderna). Las aproximaciones son extremadamente rápidas en todos los tamaños y funcionan para números mucho mayores, pero todos tienen una idea diferente de lo que significa "grande".
acaba de hacer su tamiz segmentado. y, definitivamente, Eratosthenes. –
http://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number – drdaeman