[PYTHON] Ejercicio de novato

[K4sS-]

Estoy buscando un numero primo que al dividir un numero dado entre dicho numero primo de de resto 0, y que este sea el mas alto posible.

Código [Seleccionar] Expandir

a = 600851475143
for n in range(int(a**0.5),2,-1):
    if (2**n-2)%n==0 and a%n == 0:
        sol = n
        break

print sol


Este codigo no se si está mal o bien, no da error, simplemente se queda pensando al compilarlo y asi lleva 1 hora y media. ¿Por qué?

El algoritmo consiste en:
- Utilizar un range inverso que empiece con la raiz cuadrada del numero buscado (ya que un numero primo divisor del numero dado nunca va a ser mayor que la raiz cuadrada de este) e ir hacia abajo en pasos de -1.

- Pasar saber si es primo utilizo (2**n-2)%n == 0 , es una propiedad rara de las matematicas, si un número cumple eso, es primo

- Y para saber si dicho numero primo da de resto 0 al numero que me dan hago a%n ==0

- Si cumple las dos condiciones necesarias entonces la solucion es ese primo, y salgo del bucle.

Yo pensaba que mi range si que estaba optimizado por que en cuanto encuentra 1 sale. No los coge todos si no que como quieres el mas grande vas del mas grande al mas pequeño entonces sales del bucle en cuanto encuentras uno.

Lo he probado con numeros mas bajitos y funciona, pero me gustaria saber como hacerlo para que funcione con numeros muy grandes y no se quede el ordenador pensando 3 horas.

GRACIAS

[K4sS-]

Me autocontesto por si a alguien le interesa.

El codigo final es:

Código [Seleccionar] Expandir

a = 600851475143
for n in xrange(int(a**0.5),2,-1):
    if  a%n == 0 and (2**n-2)%n==0:
        sol = n
        break

print sol

El cambio ha sido utilizar xrange que no guarda todos los valores en la memoria. Y otro detalle ha sido cambiar el orden de comprobacion, he comprado primero si es divisible cosa que es mucho más rapida de hacer, asi el programa descarta mucho antes.

Saludos

[zimmerman]

No utilices break..