Project Euler Problem 5 Performance

Question

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))

Answer 1

You should care about prime factors. Take the prime factors of one to ten, and 2520:

• 1: none
• 2: 2
• 3: 3
• 4: 2, 2
• 5: 5
• 6: 2, 3
• 7: 7
• 8: 2, 2, 2
• 9: 3, 3
• 10: 2, 5
• 2520: 2, 2, 2, 3, 3, 5, 7

You should notice that each prime factor appears in all the divisors. So, 2520 is divisible by 8, as it contains the factors 2, 2, and 2. The remainder will be the product of 3, 3, 5, and 7.

And so you should make a naive prime factors function. After that, you want to get the prime factors of the divisors, and make a dictionary of prime factors for the smallest multiple of the divisors.

Where a simple solution such as the following, is 20000 times faster than the code in your question.

import collections
from operator import mul
from functools import reduce


def prime_factors(num):
    div = 2
    while num > 1:
        if num % div:
            div += 1
            continue
        yield div
        num /= div


def gen_smallest_divisable(divisors):
    factors = collections.defaultdict(int)
    Counter = collections.Counter
    for divisor in divisors:
        div_factors = Counter(prime_factors(divisor))
        for number, amount in div_factors.items():
            factors[number] = max(factors[number], amount)
    return reduce(mul, (n ** a for n, a in factors.items()))

def smallest_multiple(multiple):
    return gen_smallest_divisable(range(1, multiple + 1))

---

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.

Just take it at face value, calling functions is slow. Also comprehensions do some magic when passed to the AST, which may speed them up. But 6 seconds for the creation of 11650000 stack frames doesn't seem unreasonable to me.

If you wanted to stick with your method, I'd highly recommend you use itertools.count, as then you don't need your recursion. And you won't test a couple thousand numbers after finding your match.

I'd also make a divisors list, to simplify things. Which has a performance cost, due to using any.

import itertools

def smallest_factor(start):
    divisors = range(11, 21)
    options = (i for i in itertools.count(start, 20)
               if not any(i % d for d in divisors))
    return next(options)

Answer 2

Only powers of primes matter

Another thing you could note is that the only factors that matter are the primes' largest powers. For example, for \$n=10\$:

• 8 = 2*2*2
• 9 = 3*3
• 5 = 5
• 7 = 7
• results in 2520 = 2*2*2 * 3*3 * 5 * 7

You can get an \$O(n\log{}\log{}n)\$ solution using a this insight.

1. First sieve all the primes less than or equal to \$n\$: sieve of eratosthenes - the slow part

2. Then find their largest power less than \$n\$.

3. And finally multiply those powers together

.

def prime_sieve(n):
    is_prime = [True] * n

    for i in range(2, n):
        if is_prime[i]:
            yield i
            for j in range(i**2, n, i):
                is_prime[j] = False

def power_less_than(n, m):
    p = n
    while p < m:
        p *= n
    return p // n

def smallest_multiple(n):
    multiple = 1
    for p in prime_sieve(n + 1):
        multiple *= largest_power_less_than(p, n + 1)
    return multiple

This solution is very fast and can handle inputs up to around \$10^6\$.

---

Some notes

• Conventional python is snake_case for variable and method names - python style guide

• Use a generator expression instead of list comprehension. You only want the smallest multiple, but the list comprehension will end up checking every number in your range. All you need to do is change the [] to () - SO question about the difference