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.
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
Mostrar Mensajes
