[Python 2.6] Funcion generadora de Numeros primos (5.761.455 primos en 19 seg)

[katas]

Buenas a todos, este es mi primer post y espero que les guste. Hace poco que he empezado a programar en python y de las primeras funciones que se me ocurrieron fue una que generase numeros primos.

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 [Seleccionar] Expandir

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()
Esta en ingles por que me gusta mas asi , 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 [Seleccionar] Expandir

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'
Sigo buscando una funcion mas potente, por que me compre hace poco una calculadora grafica muy potente que viene con una funcion isprime que hizo un calculo que mi ordenador tardo 1 hora en 0.5 segundos. Si alguien conoce como podria ser esa funcion isprime (que tambien esta en el programa matematicas de microsoft) por favor que lo comparta con todos   . Siento no haber podido añadir comentarios, quizas a muchos os cueste entender que hace la funcion, cuando tenga tiempo intentare añadirlos.

Saludos.

[leogtz]

¿Qué algoritmo sigues para la generación de los primos?

[Novlucker]

... hasta llegar al metodo de la Criba de Eratóstenes (Sieve en inglés)http://es.wikipedia.org/wiki/Criba_de_Erat%C3%B3stenes.