¿Cuál es el algoritmo más rápido conocido que genera todos los números primos distintos menores que n?
¿Es más rápido que Tamiz de Atkin ?
Por qué "entonces no", no lo entiendo.
Respuestas
¿Demasiados anuncios?
Vincent
Puntos
5027
¿Cuál es el algoritmo más rápido conocido que genera todos los números primos?
Supongo que quieres decir: Dado $n$ ¿Cuál es el algoritmo más rápido conocido que genera todos los números primos? $p \le n$ ? Actualmente es el Tamiz de Atkin .
¿Y cuál es el algoritmo más rápido conocido que genera cualquier subconjunto infinito de los números primos?
De nuevo, supongo que se refiere a: Dado $n$ ¿Qué tan rápido puedo generar $n$ ¿primas distintas? Puede que haya un método más rápido que el Tamiz de Atkin, pero no conozco ninguno. ¡Una buena pregunta!
¿Y existe un O(n) teórico lo más bajo posible de tales programas?
Es $n$ el número de primos que quieres generar? Entonces se necesitaría $O(n)$ operaciones sólo para almacenarlas en la memoria. Así que sí. Pero si quieres generar todos los primos $p \le n$ el tamiz de Atkin tiene una complejidad de tiempo $O(n/\log \log n)$ . Así que no.
menor complejidad sólo significa que dado un n suficientemente grande un algoritmo se desempeñará mejor que el otro, pero eso no significa que para un n pequeño como 10^9 ese será siempre el caso.
Sohaib I
Puntos
196
Hace poco me topé con una lógica particular. Todos los números primos caen en múltiplos de 6n+1 o 6n-1 excepto el 2 y el 3.
De este modo, el espacio de búsqueda podría reducirse considerablemente para aplicar cualquier criba como la de Atkins o Eratóstenes. De ahí que sea una forma ligeramente mejor de encontrar primos.
@sohaib, en esencia basta con considerar 2/6 = 1/3 de N para obtener todos los primos por debajo de N (ya que sólo hay que considerar las dos progresiones (6k+1) y (6k-1) y añadir 2 al final para tener en cuenta los primos 2 y 3. Incluso se puede escribir pi(n)+c(n)=N/3. Aquí, c(n) es el número de compuestos dentro de las dos progresiones. Y hay una manera fácil de obtenerlos si se trabaja con índices en lugar de números.
Badal
Puntos
11
AdZach92
Puntos
18
Los números Impares pueden ser girados en las multiplicaciones para dar salida sólo a los números Impares compuestos. Entonces los números Impares que no salen son los números primos.
Ahora cada bucle interno puede detenerse en una multiplicación que alcance el valor de un límite superior y el bucle externo puede detenerse en la raíz cuadrada del límite superior.
Además los bucles a partir del número 11 pueden incrementarse con 2,4,2,4,6,2,6,4,2,4,6,2,6,4,2,6,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,2,10,2,10 ... como continuación y repetición. Esto supone una gran ganancia de rendimiento porque los múltiplos de 3, 5 y 7 se eliminan de la secuencia de números impar.
Una aplicación de números primos realmente funciona mejor cuando se obtienen números primos entre un límite superior y el límite superior - n. Entonces la aplicación parece estar simplemente desplazando secciones (o saltando a secciones) de una lista en cada cálculo. Y en este caso los incrementos del bucle son realmente necesarios sólo en el bucle exterior porque una sola operación de división salta sobre secciones innecesarias del bucle interior. Por supuesto, las ubicaciones de los subíndices de los arrays pueden trabajar con traducciones de tal manera que el mismo array puede manejar cualquiera de los cálculos segmentados y entonces no usar mucha memoria.
1 votos
No se pueden generar todos los números primos ni un subconjunto infinito de todos los números primos en tiempo finito...
4 votos
Bien, es hora de reabrir
0 votos
La criba de Eratóstenes, como referencia, requiere un tiempo O(n)+P(n)(n/k) y un espacio P(n)log(n)+k. Aplica el tamiz de forma iterativa a los siguientes k números; para cada primo lleva la cuenta del menor múltiplo primo que hayas visto.