I'm hoping for suggestions of a concise way to write my list comprehension filter in the first solution.
I would also appreciate insight on the underlying reasons for some performance differences in my solutions for Problem 5 (https://projecteuler.net/problem=5):
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?
This first solution takes around 1.5 seconds on my laptop and the other takes 7.5 seconds.
#Project Euler problem 5
import time
start = time.time()
def smallestFactor(start):
#list comprehension filters out numbers not divisible by 11-20
options = [i for i in range(start, start + 1000000, 20)\
if i % 20 == 0 and i % 19 == 0 \
and i % 18 == 0 and i % 17 == 0 \
and i % 16 == 0 and i % 15 == 0 \
and i % 14 == 0 and i % 13 == 0 \
and i % 12 == 0 and i % 11 == 0]
#return if LCM found
if len(options) > 0:
print(options[0])
return options[0]
#recursion with larger numbers if not found
else:
smallestFactor(start + 1000000)
smallestFactor(2520)
end = time.time()
print("Speed: " + str(end - start))
My second solution instead uses a function as the list filter. The speed difference may be trivial, but I'm curious about why it takes longer to invoke a function which otherwise performs a similar filtering task as a series of conditionals written directly into the list comprehension.
#Project Euler problem 5
import time
start = time.time()
factors = [i for i in range(20,9,-1)]
def check(num):
#loop 20-11
for n in factors:
#check modulus, break or return at end of list
if num % n == 0 and n != factors[len(factors) - 1]:
continue
if num % n == 0 and n == factors[len(factors) - 1]:
return num
else:
break
def smallestFactor(start):
#list comprehension filters out numbers not divisible by 11-20
options = [i for i in range(start, start + 1000000, 20) if check(i) == i]
#return if LCM found
if len(options) > 0:
print(options[0])
return options[0]
#recursion with larger numbers if not found
else:
smallestFactor(start + 1000000)
smallestFactor(2520)
end = time.time()
print("Speed: " + str(end - start))