El tutorial o código que hallarás en este artículo es la resolución más sencilla y válida que hallamos a tus dudas o dilema.
Solución:
El tamiz de Atkin es probablemente lo que está buscando, su límite superior de tiempo de ejecución es O (N/log log N).
Si solo ejecuta los números 1 más y 1 menos que los múltiplos de 6, podría ser aún más rápido, ya que todos los números primos por encima de 3 están a 1 de algún múltiplo de seis. Recurso para mi declaración
Recomiendo un tamiz, ya sea el Tamiz de Eratóstenes o el Tamiz de Atkin.
La criba o Eratóstenes es probablemente el método más intuitivo para encontrar una lista de números primos. Básicamente tú:
- Escriba una lista de números desde 2 hasta el límite que desee, digamos 1000.
- Tome el primer número que no esté tachado (para la primera iteración es 2) y tache todos los múltiplos de ese número de la lista.
- Repita el paso 2 hasta llegar al final de la lista. Todos los números que no están tachados son primos.
Obviamente, se pueden hacer bastantes optimizaciones para que este algoritmo funcione más rápido, pero esta es la idea básica.
El tamiz de Atkin usa un enfoque similar, pero desafortunadamente no sé lo suficiente para explicárselo. Pero sé que el algoritmo que vinculé tarda 8 segundos en calcular todos los números primos hasta 1000000000 en un antiguo Pentium II-350.
Tamiz de código fuente de Eratóstenes: http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/
Código fuente de la criba de Atkin: http://cr.yp.to/primegen.html
Esto no va estrictamente en contra de la restricción de codificación, pero se acerca terriblemente. ¿Por qué no descargar programáticamente esta lista e imprimirla?
http://primes.utm.edu/lists/small/10000.txt