Euler 5 (Python)

Enunciado 5

Solución

La solución fue obtenida ejecutando el siguiente programa Python 2.5.2:

from math import sqrt

from operator import mul, add



def primo(n):

    for i in xrange(2,int(sqrt(n))+1):

        if n % i == 0:

            return False

    return True



def factorizar(n):

    primos = [x for x in xrange(2,n+1) if primo(x)]

    factores = []

    if n == 1:

        return [1]

    for p in primos:

        if n == p:

                factores.append(p)

                return factores

        if n % p == 0:

                n /= p

                factores.append(p)

                while n % p == 0:

                    n /= p

                    factores.append(p)

    return factores



def mcm(l):

    '''Maximo comun multiplo'''

    ff = [factorizar(i) for i in l]

    singles = list(set(reduce(add,ff)))

    temp = []

    for s in singles:

        temp.extend([s] * max([f.count(s) for f in ff]))

    return reduce(mul,temp,1)



if __name__ == '__main__':

    #print mcm(range(1,11))

    print mcm(range(1,21))

Python tips

• El módulo operator tiene varias funciones útiles equivalentes a operadores como * y + que pueden utilizarse con funciones como reduce, cuyo primer parámetro es una función.
• reduce toma una función f de dos argumentos y una lista l. Aplica f a los dos primeros elementos de la lista y obtiene un resultado, luego aplica la función f al resultado con el tercer elemento de la lista, y así sucesivamente hasta consumir toda la lista y retornar el resultado final. Opcionalmente se le puede pasar un tercer parámetro para que la primer llamada a la función f sea aplicada sobre este y el primer elemento de la lista.