Busqueda de Primos Criba E. Python (Optimizada)

Este algoritmo es valido para números bastante grandes, lo probé hasta con 12 cifras y demoraba unos 12 segundos en un core2duo 2.13

El algoritmo busca el siguiente primo a partir del número que se le ingrese y cuenta con algunos truquitos que implementé para optimizarlo casi un 70%

El Algoritmo está muy comentado para que se pueda entender.

#!/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))
 
 i = breaker
 while (i < lista_p_len):
  if (lista_p[i] >= raiz_raiz):
   breaker = i;
   break; 
  i+=1
 
 ultimo_numero += 1
 while (ultimo_numero <= raiz):
  n = 0
  while (n < breaker): # Todas las posiciones debajo de breaker
   modulo = ultimo_numero%lista_p[n]
   if (modulo == 0):
    break
   elif (n == breaker-1):
    lista_p.append(ultimo_numero)
    modulo_numero = numero%ultimo_numero
    if (modulo_numero == 0):
     return False
   n+=1
  ultimo_numero += 1
  
 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)):
            print "Primo encontrado... "
            break
        n += 1

if __name__ == "__main__":
    main()

Dejo el archivo para su descarga http://pastebin.com/eYqv70q2