¿Cuál es la más eficiente algoritmo para la búsqueda de números primos que pertenece al intervalo de $(p,p^2)$ donde $p$ es arbitraria en el primer número? He escuchado Tamiz de Atkin , pero ¿hay alguna manera mejor para tal caso específico que he descrito?
Respuesta
¿Demasiados anuncios?
Adam Kahtava
Puntos
383
Este es esencialmente el mismo como pidiendo los números primos por debajo de x para cualquier x.
Fundamentalmente, existen sólo dos prácticas tamices para la tarea: Eratóstenes y Atkin-Bernstein. Prácticamente, la criba de Eratóstenes es más rápido; el Atkin-Bernstein tamiz podría adelantar finalmente, pero no sé de ninguna de las implementaciones que son eficientes para números grandes.
A menos que su rango es muy pequeño, no caben en la memoria. En ese caso es importante utilizar una segmentación del tamiz; ambos Eratóstenes y Atkin-Bernstein hacer esto de forma natural.
Si usted está buscando para un programa ya existente, intente yafu, primesieve, o primegen. Los dos primeros son modificados tamices de Eratóstenes y el último es un Atkin-Bernstein aplicación, aunque eficaz sólo a $2^{32}$ (p = 65521 en su caso).
