Mostrar Temas
Al principio como todo el mundo hice una muy sencillita que tardaba aproximadamante un minuto en hacer todos los primos del 1 al millon, luego mirando funciones que encontre por internet fui perfeccionando la funcion hasta llegar al metodo de la Criba de Eratóstenes (Sieve en inglés)http://es.wikipedia.org/wiki/Criba_de_Erat%C3%B3stenes.
Esta función es bastante mas rapida y eficaz que las demás, aqui dejo un archivo python entero que junto con la funcion mide el tiempo que esta tarda en generar los primos y da bastante informacion durante el proceso que nos puede hacer una idea de la tardanza en caso de meter numeros muy altos. En el tiempo que mide esta incluido el que tarda en escribir el archivo de texto.
En el script vienen dos funciones mas que hice para el porcentaje y para medir numeros, esta ultima es para poder poner varios 0 delante de un numero primo menor que el mayor que ha descubierto la lista(vaya lio XD) por ejemplo: si hacemos del 1 al 15, para que no quede:
2
3
5
7
11
13
Pongo ceros delante de los numeros de menor cifra que el mayor (13), y queda:
02
03
05
07
11
13
Era una simple cuestion de estetica, me gustaba mas asi pero para gustos hay colores... la variable mc no tiene que ver con los primos, es la que pone los ceros (mc = '%s'%('%c0%dd' %('%',medirnum(raiz-1)))) por si pensais que esta haciendo algun calculo relacionado con el generador de la lista.
Código:
import os
import time
def PList(n,low=1,op='list'):
if (n<low) | (n<2) | (low<0): return []
iLow = low
low = low/2*2+1
print'CREATING SIEVE...',
primes = [True]*((((n+1)/2*2+1)-low)/2)
print'\rCREATING SIEVE...........................FINISHED'
raiz = int(n**0.5)+1
dim = len(primes)
m = 3
mc = '%s'%('%c0%dd' %('%',medirnum(raiz-1)))
while m < raiz:
print '\rREMOVING COMPOSITE NUMBERS OF: %s... %6.2f%c' %(mc %(m),GivePercent(m,3,raiz-1 ),'%'),
i = (m*m-low)/2
if i<0: i += m*int((0-i)/m)
if i<0: i += m
primes[i:n+1:m] = [False]*((((dim-1)-i)/m)+1)
m += 2
print'\rREMOVING COMPOSITE NUMBERS...............FINISHED '
print'REMOVING FALSES FROM LIST...',
primes = [low+(x*2) for x in xrange(dim) if primes[x]]
print'\rREMOVING FALSES FROM LIST................FINISHED'
if (iLow == 1)|(iLow==0):
primes[0]=2
if iLow == 2:
primes = [2]+primes
if op=='file':
fichero = open('PrimesList_%d-%d.txt'%(iLow,n),'w')
mc = '%c0%dd'%('%',medirnum(primes[len(primes)-1]))
mc2 = '%c0%dd'%('%',medirnum(len(primes)))
dim = len(primes)-1
for index in range(0,len(primes)):
if index%10000==0: print'\rWRITING FILE... %6.2f%c'%(GivePercent(index,0,dim),'%'),
msg = '%s>>>%s\n'%(mc2,mc)
fichero.write(msg%(index+1,primes[index]))
fichero.close()
print'\rWRITING FILE.............................FINISHED'
elif op=='print':
print'Primes from %d to %d:\n'%(iLow,n)
mc = '%c0%dd'%('%',medirnum(primes[len(primes)-1]))
mc2 = '%c0%dd'%('%',medirnum(len(primes)))
for index in range(0,len(primes)):
msg = '%s>>>%s\n'%(mc2,mc)
print msg%(index+1,primes[index])
elif op=='list': return primes
else: return 'ERROR: not a valid option'
def GivePercent(num, numinitial, nummax):
if num==numinitial==nummax: return 100.00
numero = nummax-numinitial
porcentaje = (num-numinitial)*100.00/numero
return porcentaje
def medirnum(num):
contador = 0
while num != 0:
num = num/10
contador += 1
return contador
def clear():
os.system(['clear','cls'][os.name == 'nt'])
print'------------------------------------------------------------------------------'
print'-----------------------------PRIME LIST GENERATOR--------------------by-katas-'
print'------------------------------------------------------------------------------\n'
print'Search primes from: ',
low = int(raw_input())
print'To: ',
n = int(raw_input())
clear()
print'STARTING PRIMES SEARCH FROM %d TO %d:\n'%(low, n)
start = time.time()
primes(n,low,'file')
stop = time.time()
delay = stop - start
h = int(delay/3600); m = int((delay-(3600*h))/60); s = float((delay-(3600*h))-(m*60))
print'\nSEARCH COMPLETED IN --> %04dh %02dm %02.3fs'%(h,m,s)
print'\nPress any key...'
raw_input()
, si os fijais al final de la funcion hay varias opciones que podeis pasar por parámetro: 'list' devuelve el array con la lista de primos; 'print' imprime en pantalla la lista encontrada cuando ha terminado la funcion (no la recomiendo si son muchos primos); 'file' guarda la lista en un archivo txt en el mismo directorio en el que se encuentre el script (lo recomiendo si vais a generar listas muy grandes, y a veces ni el block de notas puede con ellas asi que recomiendo abrir esas listas con el notepad++ u otro). Por cierto el primer parametro es el numero mas alto, por ejemplo si quereis calcular del 100 al 1000 tendrias que poner estos parametros (1000,100).En mi ordenador esta funcion hayo los primeros 5.761.455 numeros primos (del 1 al 100.000.000) en 19 segundos (39 segundos si escribimos un archivo txt). Necesite el Notepad++ para ver el txt por que pesaba mas de 100 mb xD.
Aqui dejo la funcion mas limpia (que no da informacion):
Código:
def PList(n,low=1,op='list'):
if (n<low) | (n<2) | (low<0): return []
iLow = low
low = low/2*2+1
primes = [True]*((((n+1)/2*2+1)-low)/2)
raiz = int(n**0.5)+1
dim = len(primes)
m = 3
while m < raiz:
i = (m*m-low)/2
if i<0: i += m*int((0-i)/m)
if i<0: i += m
primes[i:n+1:m] = [False]*((((dim-1)-i)/m)+1)
m += 2
primes = [low+(x*2) for x in xrange(dim) if primes[x]]
if (iLow == 1)|(iLow==0):
primes[0]=2
if iLow == 2:
primes = [2]+primes
if op=='file':
fichero = open('PrimesList_%d-%d.txt'%(iLow,n),'w')
mc = '%c0%dd'%('%',medirnum(primes[len(primes)-1]))
mc2 = '%c0%dd'%('%',medirnum(len(primes)))
for index in range(0,len(primes)):
msg = '%s>>>%s\n'%(mc2,mc)
fichero.write(msg%(index+1,primes[index]))
fichero.close()
elif op=='print':
print'Primes from %d to %d:\n'%(iLow,n)
mc = '%c0%dd'%('%',medirnum(primes[len(primes)-1]))
mc2 = '%c0%dd'%('%',medirnum(len(primes)))
for index in range(0,len(primes)):
msg = '%s>>>%s'%(mc2,mc)
print msg%(index+1,primes[index])
elif op=='list': return primes
else: return 'ERROR: not a valid option'
. Siento no haber podido añadir comentarios, quizas a muchos os cueste entender que hace la funcion, cuando tenga tiempo intentare añadirlos.Saludos.