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

Question

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 coding a solution for problem #5. The problem is,

"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've checked around some, and I haven't been able to find anything on this problem pertaining to Python specifically. There were some completed scripts, but I want to avoid looking at other's code in full, if possible, instead wanting to improve my own.

The code I have written runs successfully for the example of 2520 and the range 1 to 10, and should be directly modifiable to work with the question. However, upon running it, I do not get an answer. Presumably, it is a very high number, and the code is not fast enough. Printing the current number being checked seems to support this, reaching several million without getting an answer.

The code, in it's current implementation is as follows:

rangemax = 20
def div_check(n):
    for i in xrange(11,rangemax+1):
        if n % i == 0:
            continue
        else:
            return False
    return True

if __name__ == '__main__':
   num = 2
   while not div_check(num):
       print num
       num += 2
   print num

I have already made a couple changes which I think should help the speed. For one, for a number to be divisible by all numbers 1 to 20, it must be even, as only even numbers are divisible by 2. Hence, I can increment by 2 instead of 1. Also, although I didn't think of it myself, I found someone point out that a number divisible by 11 to 20 is divisible by 1 to 10. (Haven't checked that one, but it seems reasonable)

The code still, however is not fast enough. What optimisations, either programmatic, or mathematics, can I make to make this code run faster?

Thanks in advance to any who can help.

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