Skip to content
marzo 28, 2012 / dracux

Matemática y Programación III: Números Primos, Haciendolo más rápido!

Esto es algo que pensaba mientras lavaba los platos.

Si recuerdan, nuestra última versión hacía un for que iba desde 2 hasta el número a verificar/2. Esto tiene 2 problemas, uno menor y el otro bastante grave.

1-Baja prioridad: Para que verificar si divide por 2? Podría comenzar desde el 3, si yo ya había descartado los pares?

2-Alta Prioridad: Y como no dijimos que los pares no van a ser visitados, para que estabamos comprobando si dividían por pares??? Ya sabemos que eso no puede pasar, los únicos números que entran al for son impares, por ende no va a dar 0 el resto de las divisiones. Entonces podríamos modificar el for, y nuestro programa se evitaría la mitad de las cuentas que tiene que hacer.

from datetime import *
flag=0
nro=input ("Ingrese nro.:")
print "Hora de inicio: "+str(datetime.today())
if(nro%2==0 and nro!=2):
    flag=1
else:
    nroinicial=(nro+1)/2
if (nro==1): #1 no es primo
    flag=1

if (flag==0):
    if(nro!=2): #2 es primo
        for i in range (3,nroinicial+1,2):
            if(nro%i==0):
                print "Nro. "+str(nro)+" is divisible by "+str(i)+""
                flag=1
                break
if (flag==0):
    print "El nro. "+str(nro)+ " es primo."
else:
    print "El nro. "+str(nro)+ " no es primo."
print "Hora de fin: "+str(datetime.today())

En fin, se que aun lo puedo tunear más, pero volvamos a probar lo de antes:

Hora de inicio: 2012-03-27 23:58:43.365000
El nro. 10007 es primo.
Hora de fin: 2012-03-27 23:58:43.373000

8 centésimas menos que en la anterior… como que se redujo mucho la velocidad.

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: