Algoritmo rápido para encontrar el número de números primos entre dos números

Question

Mi problema se reduce a encontrar el número de números primos entre dos números dados. Podría tener un rango tan grande como 1 to (1000)! y, por lo tanto, necesito algunas optimizaciones matemáticas.

Claramente, el método de tamizado sería demasiado lento en este caso. ¿Hay alguna optimización matemática que pueda aplicarse, como por ejemplo, tomar un subconjunto más pequeño de este gran espacio y hacer inferencias sobre el resto de los números.

P.S: Definitivamente parece que podría haber llegado a un callejón sin salida, pero todo lo que estoy buscando son algunas optimizaciones que podrían ayudar a resolver esto. Y también, solo estoy buscando un enfoque de subproceso único.

EDIT: Un enfoque que he estado pensando y que puede resolver una gran cantidad de problemas relacionados con los números primos principales, es que alguien mantenga una tabla global de primos y la ponga a disposición para la búsqueda. La gente en el proyecto PrimeGrid puede contribuir de manera útil a esto.

Answer 1

Dado que desea ir tan alto como 1000! (factorial). No podrá obtener resultados exactos con los métodos actualmente conocidos en la tecnología actual.

El Prime Counting Function solo se ha evaluado exactamente para un puñado de valores hasta 10^24. Así que de ninguna manera podrás presionar 1000!.

---

Pero ya que usted menciona que una aproximación puede estar bien, puede utilizar la Logarithmic Integral como una aproximación a la función de cuenta Prime.

Esto se basa en el Prime Number Theorem que dice que la función de recuento principal es asintótica al Logarithmic Integral.

Answer 2

El método más rápido que conozco sería eliminar todos los no primos conocidos (números pares, todos los números con divisores más bajos que el número de inicio en el rango, etc.) lo más rápido posible, luego iterar el resto y use algo como el Euclidean algorithm para determinar si ese número es primo.

Answer 3

Puede examinar sus opciones aquí: http://en.wikipedia.org/wiki/Prime_counting_function

Esto también parece útil: http://mathworld.wolfram.com/PrimeCountingFunction.html

¿Puedo preguntar por qué lo necesita hasta 1000! ? Parece que nadie ha contado tantos antes. Hay 1,925,320,391,606,803,968,923 primos de 1-10^23. 1000! = 10^120. Tengo curiosidad ahora.

Answer 4

Hay un fast, simple approximation en el número de primos por debajo de un límite dado. Si no necesita valores exactos, una diferencia de dos evaluaciones de esta fórmula lo acercará.

Answer 5

El algoritmo de recuento principal desarrollado por Lagarias y otros, citado por otros, se ejecuta muy aproximadamente en O (n^(2/3)). Como un tamiz para los números primos de k1 a k2 toma aproximadamente O (máx (sqrt (k2), k2 - k1), usted verificará a qué distancia están separados sus límites inferior y superior y hará un tamiz o utilizará el algoritmo de recuento principal , el que sea más rápido

BTW. El algoritmo de recuento de cebadores se puede sintonizar para contar los números primos 1 a n para varios valores n que están razonablemente cerca más rápido que contarlos individualmente.(Básicamente, elige un número N, crea un tamiz de tamaño n/N y busca valores N^2 en ese tamiz. El O (n^(2/3)) proviene del hecho de que para N = n^(1/3) ambas operaciones toman N^(2/3) pasos. Ese tamiz se puede reutilizar para diferentes n, pero se deben buscar valores diferentes. Por lo tanto, para k valores diferentes de n, se hace N un poco más pequeño, aumentando el costo del tamiz (una sola vez) pero reduciendo el costo de la búsqueda (k veces)).

¡Para n alrededor de 1000 !, no hay ninguna posibilidad. Ni siquiera puede contar el número de primos en [n, n] para valores de ese tamaño si n no tiene factores pequeños (ish).