Project Euler getting smallest multiple in python
Question: I am doing problem five in Project Euler: "2520 is the smallest number that
can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the
numbers from 1 to 20?"

I have constructed the following code which finds the correct value 2520 when
using 1 - 10 as divisors but code seems to be going on forever when using 1 -
20. Again I don't want the code just a pointer or two on where I am going
wrong. Thanks

    
    
    def smallestDiv(n):
        end=False
        while end == False:
            divisors = [x for x in range(1,21)]    # get divisors
            allDivisions = zip(n % i for i in divisors)    # get values for  n % all integers in divisors
            check = all(item[0]  == 0 for item in allDivisions )   # check if all values of n % i are equal to zero
            if check:         # if all values are equal to zero return n
                end = True
                return n
            else:             # else increase n by 1
                n +=1
    

EDIT:

I used some code I found relating to LCM and used reduce to solve the problem:

    
    
    def lcm(*values):
        values = [value for value in values]
        if values:
            n  = max(values)
            m = n
            values.remove(n)
            while any( n % value for value in values ):
                n +=m
            return n
        return 0
    
    print reduce(lcm, range(1,21))
    


Answer: If a problem is hard, trying solving a simpler version. Here, how to calculate
the lowest common multiple of _two_ numbers. If you've read any number theory
book (or think about prime factors), you can do that using the greatest common
divisor function (as implemented by the Euclidean algorithm).

    
    
    from fractions import gcd
    def lcm(a,b):
        "Calculate the lowest common multiple of two integers a and b"
        return a*b//gcd(a,b)
    

Observing `lcm(a,b,c) ≡ lcm(lcm(a,b),c)` it's simple to solve your problem
with Python's
[`reduce`](http://docs.python.org/2/library/functions.html#reduce) function

    
    
    >>> from functools import reduce
    >>> reduce(lcm, range(1,10+1))
    2520
    >>> reduce(lcm, range(1,20+1))
    232792560
    

