¿Cuál es el algoritmo más eficiente para encontrar todos los números primos entre dos números arbitrarios dados?

Tabla de búsqueda.

Lista de números primos hasta 1000000000000

(Sí, me fue mucho mejor en mis clases de ingeniería que en mis clases de algoritmos. ¿Cómo lo sabías?)

Un método simple pero efectivo para generar números primos entre A y B grandes es hacer el tamiz primario normal (Eratóstenes) hasta [math] \ sqrt {B} [/ math] y usarlos para tamizar el intervalo [A, B] . Para esto, toma cada primer p y elimina todos los múltiplos comenzando desde [math] \ lceil A / p \ rceil p [/ math] a [math] \ lfloor B / p \ rfloor p [/ math].

Los dos algoritmos más eficientes (que yo sepa) para calcular números primos, dado un rango, son Sieve of Atkin y Sieve of Eratosthenes.

Puede darles una oportunidad a ambos y elegir uno según su aplicación y comodidad.

Tabla hash ordenada de todos los primos calculados previamente.

Esto le permite determinar la primalidad en O (1) tiempo y O (n) espacio. Dado que la tabla hash está ordenada, simplemente puede hacer un escaneo de rango secuencial sobre el espacio de búsqueda después de identificar el primer y último primo en la secuencia. Dado que la relación de primos a no primos es logarítmica, la exploración de rango tomaría tiempo O (log n).

Tamiz de Eratóstenes es O (n log log n) tiempo.

Como regla general, el espacio es barato y el tiempo no.

Por supuesto, si está hablando de números primos ridículamente grandes (claves de criptografía de IE) necesita una cantidad de espacio increíble (número de bytes en el orden del número de átomos en el universo observable) o una cantidad de tiempo increíble (mayor que la edad del universo). La intratabilidad del problema es lo que hace que la criptografía (clave pública) sea segura.

  primeList = []

 def primeNumFinder (inicio, fin):
     para i en rango (inicio, fin):
         p = 0        
		 para j en rango (inicio, fin):
              si i% j es 0:
                  p + = 1        
	 si p es 1:
        primeList.append (i)

 primeNumFinder (2, 10000000000)
 print (len (primeList))
 print (primeList)

Ese es un código de un lenguaje Python … enumerará todos los que ingrese en esa función primeNumFinder … diviértase: D

No sé cuál es el más eficiente, pero Sieve of Eratosthenes es bueno para encontrar primos pequeños con una precisión del 100%. El problema es que siempre los generará comenzando con 2. Puede cortar las respuestas adicionales para obtener su rango, aunque eso definitivamente dañaría su eficiencia en función de la cantidad de números que está tirando.