elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Rompecabezas de Bitcoin, Medio millón USD en premios


+  Foro de elhacker.net
|-+  Programación
| |-+  Scripting
| | |-+  [Python 2.6] Funcion generadora de Numeros primos (5.761.455 primos en 19 seg)
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: [Python 2.6] Funcion generadora de Numeros primos (5.761.455 primos en 19 seg)  (Leído 9,834 veces)
katas

Desconectado Desconectado

Mensajes: 1


Ver Perfil
[Python 2.6] Funcion generadora de Numeros primos (5.761.455 primos en 19 seg)
« en: 10 Marzo 2010, 00:23 am »

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:
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 :P, 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'
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   :D. Siento no haber podido añadir comentarios, quizas a muchos os cueste entender que hace la funcion, cuando tenga tiempo intentare añadirlos.

Saludos.


En línea

leogtz
. . .. ... ..... ........ ............. .....................
Colaborador
***
Desconectado Desconectado

Mensajes: 3.069


/^$/


Ver Perfil WWW
Re: [Python 2.6] Funcion generadora de Numeros primos (5.761.455 primos en 19 seg)
« Respuesta #1 en: 10 Marzo 2010, 01:28 am »

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


En línea

Código
  1. (( 1 / 0 )) &> /dev/null || {
  2. echo -e "stderrrrrrrrrrrrrrrrrrr";
  3. }
  4.  
http://leonardogtzr.wordpress.com/
leogutierrezramirez@gmail.com
Novlucker
Ninja y
Colaborador
***
Desconectado Desconectado

Mensajes: 10.683

Yo que tu lo pienso dos veces


Ver Perfil
Re: [Python 2.6] Funcion generadora de Numeros primos (5.761.455 primos en 19 seg)
« Respuesta #2 en: 10 Marzo 2010, 01:50 am »

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

;D
En línea

Contribuye con la limpieza del foro, reporta los "casos perdidos" a un MOD XD
"Hay dos cosas infinitas: el Universo y la estupidez  humana. Y de la primera no estoy muy seguro."
Albert Einstein
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Reto: Números primos en python
Ejercicios
Novlucker 6 10,417 Último mensaje 24 Noviembre 2010, 16:02 pm
por Novlucker
Programacion en C. Fallo codificar numeros primos « 1 2 »
Programación C/C++
nenito_sevillista 10 9,961 Último mensaje 24 Noviembre 2010, 22:52 pm
por do-while
NUMEROS PRIMOS
Programación C/C++
alviera 4 6,008 Último mensaje 7 Diciembre 2010, 06:39 am
por N0body
[Duda] Sacar números primos de una secuencia
Programación Visual Basic
Hurubnar 2 3,988 Último mensaje 25 Febrero 2011, 16:59 pm
por Hurubnar
Demultiplicación de números o como conseguir los dos primos q componen un num
Seguridad
erChucky 1 2,747 Último mensaje 14 Octubre 2013, 22:10 pm
por ivancea96
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines