Project Euler 5 In Python - How Can I Optimize My Solution?

I've recently been working on Project Euler problems in Python. I am fairly new to Python, and still somewhat new as a programmer. In any case, I've ran into a speed-related issue

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]

deffind_solution(step):
    for num in xrange(step, 999999999, step):
        ifall(num % n == 0for n in check_list):
            return num
    returnNoneif __name__ == '__main__':
    solution = find_solution(20)
    if solution isNone:
        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]
deffind_prime_factors(n):
    lst = []
    for p in _primes:
        n = pull_off_factors(n, p, lst)
    return lst

deffind_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 = 1for 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:

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

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

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

deflcm_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.

Solution 4:

Break down the number as a prime factorization.

All primes less than 20 are:

2,3,5,7,11,13,17,19

So the bare minimum number that can be divided by these numbers is:

2*3*5*7*11*13*17*19

Composites:

4,6,8,9,10,12,14,15,16,18,20 = 2^2, 2*3, 2^3, 3^2, 2*5, 2^2*3, 2*7, 3*5, 2*3^2, 2^2*5

Starting from the left to see which factors needed:

• 2^3 to build 4, 8, and 16
• 3 to build 9
• Prime factorization: 2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19 = 232,792,560

Solution 5:

I got the solution in 0.066 milliseconds (only 74 spins through a loop) using the following procedure:

Start with smallest multiple for 1, which = 1. Then find the smallest multiple for the next_number_up. Do this by adding the previous smallest multiple to itself (smallest_multiple = smallest_multiple + prev_prod) until next_number_up % smallest_multiple == 0. At this point smallest_multiple is the correct smallest multiple for next_number_up. Then increment next_number_up and repeat until you reach the desired smallest_multiple (in this case 20 times). I believe this finds the solution in roughly n*log(n) time (though, given the way numbers seem to work, it seems to complete much faster than that usually).

For example:

1 is the smallest multiple for 1

Find smallest multiple for 2

Check if previous smallest multiple works 1/2 = .5, so no

previous smallest multiple + previous smallest multiple == 2.

Check if 2 is divisible by 2 - yes, so 2 is the smallest multiple for 2

Find smallest multiple for 3

Check if previous smallest multiple works 2/3 = .667, so no

previous smallest multiple + previous smallest multiple == 4

Check if 4 is divisible by 3 - no

4 + previous smallest multiple == 6

Check if 6 is divisible by 3 - yes, so 6 is the smallest multiple for 3

Find smallest multiple for 4

Check if previous smallest multiple works 6/4 = 1.5, so no

previous smallest multiple + previous smallest multiple == 12

Check if 12 is divisble by 4 - yes, so 12 is the smallest multiple for 4

repeat until 20..

Below is code in ruby implementing this approach:

def smallestMultiple(top)prod=1
    counter =0
    top.times do
        counter +=1
        prevprod =prodwhileprod % counter !=0prod=prod+ prevprod
        end
    end
    returnprod
end