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()