Padraic Cunningham - 3 months ago 23

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`

function

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