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

 

 


Tema destacado: Sigue las noticias más importantes de seguridad informática en el Twitter! de elhacker.NET


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Ejercicios
| | | |-+  [PYTHON] Ejercicio de novato
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: [PYTHON] Ejercicio de novato  (Leído 4,196 veces)
K4sS-

Desconectado Desconectado

Mensajes: 19



Ver Perfil
[PYTHON] Ejercicio de novato
« en: 4 Abril 2013, 11:05 am »

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:
 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 :)


En línea

K4sS-

Desconectado Desconectado

Mensajes: 19



Ver Perfil
Re: [PYTHON] Ejercicio de novato
« Respuesta #1 en: 4 Abril 2013, 13:56 pm »

Me autocontesto por si a alguien le interesa.

El codigo final es:

Código:
 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 :)


En línea

zimmerman

Desconectado Desconectado

Mensajes: 16


Por más que caigas, siempre te puedes levantar


Ver Perfil
Re: [PYTHON] Ejercicio de novato
« Respuesta #2 en: 3 Octubre 2013, 15:34 pm »

No utilices break..
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Ayuda con C++, Ejercicio Simple [Soy Novato]
Programación C/C++
xmbeat92 3 5,018 Último mensaje 1 Octubre 2010, 07:47 am
por xmbeat92
Ejercicio de python
Ejercicios
Folazo 2 4,790 Último mensaje 25 Enero 2012, 14:52 pm
por criskapunk
Ejercicio de novato en Python3
Ejercicios
Itzhack 3 3,242 Último mensaje 24 Septiembre 2014, 16:35 pm
por Itzhack
Ayuda con ejercicio novato
Programación C/C++
ascuasflame 3 2,273 Último mensaje 3 Febrero 2018, 15:52 pm
por dijsktra
Ayuda para novato en python (no es un ejercicio)
Scripting
YuanO 0 1,933 Último mensaje 2 Junio 2022, 07:39 am
por YuanO
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines