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))
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
You are doing a brute force search, so it can get arbitrary long. You should read about LCM (least common multiple) in order to code an efficient solution.(which I believe is 232792560
)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With