¿Cómo calculo el número primo más grande más pequeño que el valor x?Algoritmo para encontrar el número primo más grande más pequeño que x
De hecho, no tiene que ser exacto, solo aproximado y cercano a x.
x es un entero de 32 bits.
La idea es que x es un parámetro de configuración. Estoy usando el número primo más grande menor que x (llámalo y) como el parámetro para un constructor de clase. El valor y debe ser un número primo.
Una buena información here sobre la función pi (x). Al parecer,
pi(x) = the number of primes less than x
y se puede aproximar pi (x) con
x/(log x - 1)
mientras
the n-th prime of that list of primes is equal to approximately n(log n)
Gracias, esto es lo que estoy buscando. Lo suficientemente cerca cuando se calcula el enésimo primo – Matt
Li de Gauss (la [función integral logarítmica compensada] (http://en.wikipedia.org/wiki/Logarithmic_integral_function)) es un estimador mucho mejor que * x */(log * x * - 1) - ¡como explica Chris Caldwell en la página enlazada! –
¡Guau, excelente respuesta y súper interesante! @GarethRees No entiendo lo que quiere decir con: > Y podemos ver de la misma manera que la función Li (x) - (1/2) Li (x1/2) es 'en promedio' una mejor aproximación que Li (x) a pi (x); pero no se puede atribuir importancia a los últimos términos en la fórmula de Riemann, ni siquiera mediante promedios repetidos. –
¿Qué tan rápido que necesita el programa se ejecuta? ¿Y con qué frecuencia calculas este problema?
Si necesita un logro rápido y no le importa la memoria. Puede generar una tabla principal creciente por método de criba y luego mantenerla durante la vida útil del programa, y luego, cuando encuentre qué 'el número primo más grande más pequeño que el valor x', simplemente mire la tabla y en el tiempo O (log N) puede encontrar una respuesta exacta.
Para rangos más pequeños de primos, esta es casi seguramente la forma más rápida de hacerlo. Todos los números primos de dos bytes (6542 de ellos) encajarán en una memoria caché L1 de 16kB si se almacenan como valores de 16 bits, y encajarán en una memoria caché L1 de 32kB si se almacenan como valores de 32 bits. Todas las CPU recientes tienen al menos un caché de datos L1 de 32kB. Los números primos 1077871 que pueden representarse con 3 bytes cada uno no encajarán en una memoria caché de 4MB L2 si se almacenan como valores de 32 bits, pero lo harán si empaqueta 5 de ellos en 16 bytes, lo que aún le permite hacer una búsqueda binaria eficiente. . – user57368
Creo que tal vez necesites saber algunos primos contextuales para resolver mejor este problema. ¿Es eso posible? X no es primo? – marklar
¿A qué escala? Enteros de 32 bits? ¿O para criar estándares como números de 1024 bits? – selbie
x va a estar en el rango int32 – Matt