Euler 3 (Python)

Posted on 7 de junio, 2009 by Juanjo

Enunciado 3

Los factores primos de 13195 son 5, 7, 13 y 29.

¿Cual es el mayor factor primo del número 600851475143?

Solución

La solución fue obtenida en el intérprete interactivo de Python 2.5.2:

>>> from math import sqrt
>>> the_number = 600851475143
>>> my_number = sqrt(the_number)
>>> my_number
775146.09922452678
>>> my_number = int(my_number)
>>> my_number
775146
>>> def esprimo(n):
...     for i in xrange(2,int(sqrt(n))+1):
...             if n % i == 0:
...                     return False
...     return True
...
>>> esprimo(8)
False
>>> esprimo(3)
True
>>> esprimo(6823)
True
>>> esprimo(100109)
True
>>> esprimo(100110)
False
>>> for i in xrange(1, my_number+1):
...      if the_number % i == 0 and esprimo(i):
...             print i
...
1
71
839
1471
6857

Python tips

  • xrange, en lugar de crear una lista entera de números como hace range devuelve un generador que va entregando números a medida que los necesitamos.
  • La clase int se instancia para obtener enteros. Si la llamamos con un float como parámetro, podemos usarla para forzar un entero.

About Juanjo

Mi nombre es Juanjo Conti, vivo en Santa Fe y soy Ingeniero en Sistemas de Información. Mi lenguaje de programación de cabecera es Python; lo uso para trabajar, estudiar y jugar. Como hobby escribí un libro de cuentos que se puede descargar gratuitamente.
This entry was posted in Aprendiendo Python, Problemas and tagged , . Bookmark the permalink.
  • Juampa

    Hola Juanjo, me puse a mirar un poco y a probar como era mi primer encuentro casual con python. Fue bien, así que aporto una ligera modificación para evitar al menos la mitad de operaciones en números grandes:

    >>> def esprimo2(n):
...     if n % 2 == 0:
...             return False
...     for i in xrange(3,int(sqrt(n))+1,2):
...             if n % i == 0:
...                     return False
...     return True
...

    Que cantidad de funciones tiene python!

    Saludos

  • Juanjo

    Buenísimo Juampa! y gracias por el agregado.

  • Juampa

    Hola Juanjo, me puse a mirar un poco y a probar como era mi primer encuentro casual con python. Fue bien, así que aporto una ligera modificación para evitar al menos la mitad de operaciones en números grandes:
    <pre>
    >>> def esprimo2(n):
    … if n % 2 == 0:
    … return False
    … for i in xrange(3,int(sqrt(n))+1,2):
    … if n % i == 0:
    … return False
    … return True
    …
    </pre>
    Que cantidad de funciones tiene python!

    Saludos