Calculo de numeros primos
En un problema que resolvi recientemente en el proyecto euler, descubrí un algoritmo sencillo para calcular numeros primos: la criba de eratóstenes El cual inicialmente traduje a python como:
1 def eratostenes(m):
2 primos = set(range(2,m+1))
3 for i in xrange(2,int(sqrt(m))+1):
4 if i in primos:
5 for j in xrange(2,m/i+1):
6 primos.discard(i*j)
7
8 return primos
No comento el código por ser una transcripción directa del algoritmo enlazado, asi que si no entiendes como funciona, mejor leer el articulo de la wikipedia.
El problema de esta solución es que para números grandes, el conjunto inicial es muy grande y se crea nada mas empezar, por lo que en caso de no tener memoria suficiente pasará lo que tiene que pasar cuando el 99% de las aplicaciones están en la partición de swap.
Por ello, cree una modificación del algoritmo de eratóstenes, para continuar un set de primos dado:
def erato_follow(m,primes):
'''
m - nuevo numero tope
primes - antiguo set de numeros primos
'''
if not primes: #si se ha llamado sin pasar un set antiguo
# se trabaja como siempre
pl = eratostenes(m)
else:
pl = primes
np = set(range(max(pl),m)) #nuevos primos
for i in xrange(2,int(sqrt(m))+1):
if i < max(pl): #aprovechamos lo aprendido
for j in xrange(2,m/i+1):
np.discard(i*j)
else: #sacamos los que quedan
for j in xrange(2,m/i+1):
np.discard(i*j)
return pl | np # union de ambos
mediante esta funcion, podemos seguir aumentando el numero de primos en incrementos manejables, si bien habrá que tener cuidado con el set completo ya que al final acabará creciendo por encima de la memoria disponible.