[Python] Optimizar busqueda de primos

[camaleonh]

Hola a todos
Este algoritmo es hasta el que he podido llegar con mayor velocidad a encontrar numeros primos, el problema es que busco encontrar un numero primo de más de 20 cifras pero demora una eternidad, entonces cualquier optimización me sirve de mucha ayuda

Código (python) [Seleccionar] Expandir

#!/usr/bin/env python

#Buscador de Numeros primos a partir de un numero dado
# Juan Fernando Hernandez
# Universidad de Antioquia - Matematicas Discretas
# uso: python eratostenes_criba.py numero_inicial

from math import sqrt
import sys

# Lista de primos y semaforo de llenado de lista
lista_p = [2]


ultimo_numero = 2
breaker = 1

# Busqueda de primos (true->primo || false->compuesto)
def primo(numero):

# si es divisible por la lista no es primo (Retorna falso)
for i in lista_p:
modulo = numero % i
if (modulo == 0): return False
# Se sabe que como el numero inmediatamente anterior en el bucle es
# menor, todos los primos de la lista < raiz de numero actual

return llenar_lista(numero)
   
def llenar_lista(numero):

global breaker
global ultimo_numero

raiz = long(sqrt(numero))
# Necesario para no comprobar todos los primos de la lista
# se establece un breaker

lista_p_len = len(lista_p)
raiz_raiz = long(sqrt(raiz))

for i in range(breaker,lista_p_len):
if (lista_p[i] >= raiz_raiz):
breaker = i;
break;

ultimo_numero += 1

for i in range(ultimo_numero,raiz+1):
for n in range(0,breaker):
modulo = i%lista_p[n]
if (modulo == 0):
break
elif (n == breaker-1):
lista_p.append(i)
modulo_numero = numero % i
if(modulo_numero == 0):
ultimo_numero = i
return False

ultimo_numero = raiz
return True



def main():

    #n = 10000000000000000000 #Numero minimo
    n = long(sys.argv[1])  # Minimo numero desde el cual buscar el proximo primo

   
    while True:
        print "Probando primo: ", n
        if(primo(n)):
            break;
        n += 1
       
    print "Primo encontrado: ", n

if __name__ == "__main__":
    main()