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

#!/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()