Project Euler 5 in Python - How can I optimize my solution?

Solution 1:

Taking the advice of Michael Mior and poke, I wrote a solution. I tried to use a few tricks to make it fast.

Since we need a relatively short list of numbers tested, then we can pre-build the list of numbers rather than repeatedly calling xrange() or range().

Also, while it would work to just put the numbers [1, 2, 3, ..., 20] in the list, we can think a little bit, and pull numbers out:

Just take the 1 out. Every integer is evenly divisible by 1.

If we leave the 20 in, there is no need to leave the 2 in. Any integer evenly divisible by 20 is evenly divisible by 2 (but the reverse might not be true). So we leave the 20 and take out the 2, the 4, and the 5. Leave the 19, as it's prime. Leave the 18, but now we can take out the 3 and the 6. If you repeat this process, you wind up with a much shorter list of numbers to try.

We start at 20 and step numbers by 20, as Michael Mior suggested. We use a generator expression inside of all(), as poke suggested.

Instead of a while loop, I used a for loop with xrange(); I think this is slightly faster.

The result:

check_list = [11, 13, 14, 16, 17, 18, 19, 20]

def find_solution(step):
    for num in xrange(step, 999999999, step):
        if all(num % n == 0 for n in check_list):
            return num
    return None

if __name__ == '__main__':
    solution = find_solution(20)
    if solution is None:
        print "No answer found"
    else:
        print "found an answer:", solution

On my computer, this finds an answer in under nine seconds.

EDIT: And, if we take advice from David Zaslavsky, we realize we can start the loop at 2520, and step by 2520. If I do that, then on my computer I get the correct answer in about a tenth of a second.

I made find_solution() take an argument. Try calling find_solution(2520).

Solution 2:

My first answer sped up the original calculation from the question.

Here's another answer that solves it a different way: just find all the prime factors of each number, then multiply them together to go straight to the answer. In other words, this automates the process recommended by poke in a comment.

It finishes in a fraction of a second. I don't think there is a faster way to do this.

I did a Google search on "find prime factors Python" and found this:

http://www.stealthcopter.com/blog/2009/11/python-factors-of-a-number/

From that I found a link to factor.py (written by Mike Hansen) with some useful functions:

https://gist.github.com/weakish/986782#file-factor-py

His functions didn't do quite what I wanted, so I wrote a new one but used his pull_prime_factors() to do the hard work. The result was find_prime_factors() which returns a list of tuples: a prime number, and a count. For example, find_prime_factors(400) returns [(2,4), (5,2)] because the prime factors of 400 are: (2*2*2*2)*(5*5)

Then I use a simple defaultdict() to keep track of how many we have seen so far of each prime factor.

Finally, a loop multiplies everything together.

from collections import defaultdict
from factor import pull_off_factors

pf = defaultdict(int)

_primes = [2,3,5,7,11,13,17,19,23,29]
def find_prime_factors(n):
    lst = []
    for p in _primes:
        n = pull_off_factors(n, p, lst)
    return lst

def find_solution(low, high):
    for num in xrange(low, high+1):
        lst = find_prime_factors(num)
        for n, count in lst:
            pf[n] = max(pf[n], count)

    print "prime factors:", pf
    solution = 1
    for n, count in pf.items():
        solution *= n**count

    return solution

if __name__ == '__main__':
    solution = find_solution(1, 20)
    print "answer:", solution

EDIT: Oh wow, I just took a look at @J.F. Sebastian's answer to a related question. His answer does essentially the same thing as the above code, only far more simply and elegantly. And it is in fact faster than the above code.

Least common multiple for 3 or more numbers

I'll leave the above up, because I think the functions might have other uses in Project Euler. But here's the J.F. Sebastian solution:

def gcd(a, b):
    """Return greatest common divisor using Euclid's Algorithm."""
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    """Return lowest common multiple."""
    return a * b // gcd(a, b)

def lcmm(*args):
    """Return lcm of args."""   
    return reduce(lcm, args)

def lcm_seq(seq):
    """Return lcm of sequence."""
    return reduce(lcm, seq)

solution = lcm_seq(xrange(1,21))
print "lcm_seq():", solution

I added lcm_seq() but you could also call:

lcmm(*range(1, 21))

Solution 3:

Since your answer must be divisible by 20, you can start at 20 and increment by 20 instead of by two. In general, you can start at rangemax and increment by rangemax. This reduces the number of times div_check is called by an order of magnitude.