Es allí una manera de encontrar el valor aproximado de la n-ésimo primo?
https://stackoverflow.com/questions/1042717
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Hay una función que devuelve el valor aproximado de la n th prime?Creo que esto sería algo así como un aproximado de la inversa de la primer función de conteo.Por ejemplo, si me dio esta función 25 volvería un número de alrededor de 100, o si me dio esta función 1000 volvería un número de alrededor de 8000.No me importa si el número devuelto es primo o no, pero quiero que sea rápido (así que no hay generación de la primera n los números primos para devolver el n th.)
Me gustaría que esta para que yo pueda generar la primera n números primos utilizando un colador (Eratóstenes o Atkin).Por lo tanto, la aproximación de n th el ideal sería que nunca se debe subestimar el valor real de la n th prime.
(Actualización:ver mi respuesta para un buen método para encontrar el límite superior de la n ésimo número primo.)
Solución
Límites más estrictos:
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 nunca deberían ser menores que el nth_prime real, deberían funcionar para cualquier entrada de 64 bits, y estar en un orden de magnitud o más cerca que la fórmula de Robin dada 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, por lo que puedo ajustar un poco más la última estimación. Técnicamente 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 conteo primo (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 el anterior (todavía 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 la enésima prima, puede hacer:
- Cipolla 1902 (ver Dusart 1999 página 12 o este documento . Encuentro tres términos (m = 2) más un factor de corrección de tercer orden para 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). Usando el inverso de dos términos li o Riemann R inverso a continuación dará mejores resultados.
- Calcule los límites superior e inferior de Dusart 2010 y promedie 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 primo, el inverso es una aproximación nth_prime decente. 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 esto se está acercando a R (n)
- R ^ {- 1} La función inversa de Riemann R es la aproximación promedio más cercana que sé que es razonable.
Por último, si tiene un método de recuento primo 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 rápido y preciso. Calcular el 10 ^ 10 ° prime se puede hacer en unos pocos milisegundos, y el 10 ^ 13th 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 más grandes, pero todos tienen una idea diferente de lo que & "; Grande &"; significa.
Otros consejos
Gracias por todas las respuestas a esas preguntas.Yo sospechaba que había algo bastante simple como eso, pero no lo pude encontrar en el tiempo.He hecho un poco más de investigación también.
Como yo lo quiero para un tamiz para generar la primera n los números primos, quiero que la aproximación de ser mayor o igual a la nth prime.(Por lo tanto, quiero que el límite superior de la nésimo número primo.)
Wikipedia da la siguiente cota superior para n >= 6
p_n <= n log n + n log log n (1)
donde p_n es el nth prime, y log es el logaritmo natural.Este es un buen comienzo, pero puede sobreestimar por una cantidad no despreciable. Este artículo en La Facultad De Matemáticas De Diario da una mayor cota superior para n >= 7022
p_n <= n log n + n (log log n - 0.9385) (2)
Esto es mucho más estrecha obligado como muestra la tabla siguiente
n p_n approx 1 error% approx 2 error%
1 2
10 29 31 6.90
100 541 613 13.31
1000 7919 8840 11.63
10000 104729 114306 9.14 104921 0.18
100000 1299709 1395639 7.38 1301789 0.16
1000000 15485863 16441302 6.17 15502802 0.11
10000000 179424673 188980382 5.33 179595382 0.10
He implementado mi nth primer aproximación de la función a utilizar la segunda aproximación para n >= 7022, la primera aproximación para 6 <= n < 7022, y una matriz de búsqueda para los 5 primeros números primos.
(Aunque el primer método no es muy apretado obligada, especialmente para el rango donde yo lo uso, no me preocupa como yo quiero esto para un colador, y de un tamiz de números más pequeños es barato de cómputo.)
El teorema de números primos proporciona una cantidad de números primos por debajo de un valor umbral, por lo que podría ser solía dar un valor aproximado para la enésima prima.
Como estimación aproximada, puede usar n * ln (n) como una aproximación para el enésimo número primo. Existe un método mucho más complejo, pero más preciso, cuyos detalles puede encontrar en Wikipedia aquí .
Mi mejor estimación Prime (n)
1/2*(8-8.7*n-n^2+
1/2*(2*abs(log(n)/log(3)+log(log(n)/log(2))/log(2))+
abs((log(log(3))-log(log(n))+2*n*log(log(n)/log(2))+
sqrt(((8*log(3)*log(n))/log(2)-log(log(2))+
log(log(n)))*log(log(n)/log(2))))/log(log(n)/log(2))))*(-1+
abs(log(n)/log(3)+log(log(n)/log(2))/log(2))+abs(-(1/2)+n+
sqrt(((8*log(3)*log(n))/log(2)-log(log(2))+
log(log(n)))*log(log(n)/log(2)))/(2*log(log(n)/log(2))))))
Aquí está mi fórmula más reciente y más experimental.
por cierto. El primo diez billonésimo es 323,780,508,946,331 esta fórmula funciona bastante bien en esa escala, no estoy seguro de si continúa acercándose a n*ln(n)+n*(ln(ln(n))-0.9385).
1/2*(3-(8+ln(2.3))*n-n^2+1/2*(-1+
abs(-(1/2)+n+sqrt(ln(ln(n)/ln(2))*(-ln(ln(2))+ln(ln(n))+
(8*ln(3)*ln((n*ln(8*n))/ln(n)))/ln(2)))/(2*ln(ln((n*ln(8*n))/
ln(n))/ln(2))))+abs(ln(n)/ln(3)+ln(ln((n*ln(8*n))/ln(n))/ln(2))/
ln(2)))*(2*abs(ln((n*ln(8*n))/ln(n))/ln(3)+ln(ln((n*ln(8*n))/ln(n))/
ln(2))/ln(2))+abs(1/ln(ln(n)/ln(2))*(ln(ln(3))-ln(ln(n))+2*n*ln(ln(n)/
ln(2))+sqrt(((8*ln(3)*ln(n))/ln(2)-ln(ln(2))+ln(ln((n*ln(8*n))/ln(n))))*
ln(ln((n*ln(8*n))/ln(n))/ln(2)))))))
Una implementación eficiente probablemente no sea posible con un tamiz. Piensa en lo que sucedería si quieres tener los primeros 10.000 números primos. Probablemente tendrías que hacer un tamiz sobre una gran cantidad de números.
Su propia implementación en esta pregunta y mi respuesta son buenas maneras de implementar esto sin conocer la aplicación. valor de una prima
Para complementar el límite superior de Dana J, esta fórmula debería darte un buen límite inferior.
P(n) = (((2 Log(3, n + 2))/(Log(2.5, 2) + Log(3, 3)) + (2 Log(3, n - 2))/(Log(3, 2) + Log(3, 3)))/2) n;
