1

So I am a new programmer, studying CS in university. I am new to Python and have been solving project euler puzzles, and I am wondering why my number 5 takes so long to compute! Looks like 287 seconds. I get the correct answer, but the compute time is very long. Can anyone explain to me why this is, and how I could better optimize it to run faster?

For anyone unfamiliar with project euler, this question is asking me to find the first positive number divisible by all numbers 1 through 20.

Edit: Thanks for all the help guys. I don't know how to comment on comments but your suggestions have been very helpful. Thanks!!

import time
def main():
    time_start = time.clock()
    x=2
    while True:
        if divBy20(x)==True:
            print(x)
            break
        else:
            x=x+1

    time_elapsed = (time.clock() - time_start)
    print(time_elapsed)

def divBy20(a):
    for i in range(1,21):
        if a%i!=0:
            return False
    return True

main()
Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
TheSalamander
  • 67
  • 9
  • 6
    You are doing lots of unnecessary work. For instance, if a number is divisible by 10, it's also divisible by 2 and 5, but you explicitly check all 3. Also, there's no need to check any odd `x`, because they won't be divisible by 2. All Project Euler problems have one thing in common: the brute force approach is *not* the correct approach. You have to think about the problem to find efficient solutions. – chepner Aug 18 '14 at 18:09
  • 2
    It'd be a good idea to check how many numbers you're actually checking, which I'm guessing is .. quite a few. :-) The secret is to minimize the amount of work needed, not attempt to do the work faster (so try to avoid brute forcing). For each number, you're doing quite a lot of work as well. – MatsLindh Aug 18 '14 at 18:10
  • You are counting from 1 to a large number, doing none-trivial work at each step. That will take a while in any language. You need a better algorithm. Hint: Try to solve the problem by hand, it's not hard. – user448810 Aug 18 '14 at 18:10
  • This is the brute force approach. Some tips, you could increment X by 2 every iteration since the final number will not be odd. Also, you could test fewer numbers(if it's divisible by any even number, you don't need to test for 2). – JustinDanielson Aug 18 '14 at 18:10
  • 3
    This will become much simpler if you notice that you're looking for the [least common multiple](http://www.mathsisfun.com/least-common-multiple.html). – bereal Aug 18 '14 at 18:16
  • Division is actually one of the slowest things a processor can do; if you want your code to run efficiently, do it as little as possible. Here's a bigger hint: this problem can be solved without testing numbers at all. The correct answer can be generated. – TheSoundDefense Aug 18 '14 at 18:16
  • This question would be more appropriate for [CodeReview](http://codereview.stackexchange.com/). That SE site is intended for the "this code works, but I want it to be better" type questions. Also, take a look at the [Python Profilers](https://docs.python.org/2/library/profile.html). Learn to use and love them. Any time you have unexpected run times or bottlenecks in a Python script, they should be your first stop to pinpoint the issue. – skrrgwasme Aug 18 '14 at 18:26
  • 2
    please note project Euler specifically asks you to look at its own forums and the answers/discussion there rather than posting to external sites. To help with their suggested approach you can also download an overview pdf after you solve the problem that discusses some possible approaches (see the about page when you are signed in). I did problem #5 today and found the pdf very well written. – TooTone Aug 18 '14 at 18:26
  • you can trivially replace `for i in range(1,21):` with `for i in [some factors]:` that should be quite faster already. determining the actual factors is left as an exercise to the reader. – njzk2 Aug 18 '14 at 18:30

3 Answers3

3

Your program loops over every possible number one-by-one until it finds the solution. This is the brute force solution. Project Euler questions are designed to foil brute force approaches. It requires cleverness to improve upon the direct approach. Sometimes that means refining your answer. Sometimes it means completely rethinking it.

Refine

This problem is a great example. You could make some incremental improvements to your algorithm. For instance, you know the answer must be even, so why not skip odd numbers?

x = x + 2

In fact, it must be divisible by 3, so we could even count in multiples of 6.

x = x + 6

And it must be divisible by 5, right? Heck, let's count 30 at a time. Now we're cooking!

x = x + 30

You could keep following this line of thinking and make the increment bigger and bigger. But this would be a good time to step back. Let's rethink this whole approach. Do we need to iterate at all? Where's this all headed?

Rethink

If we multiplied together 1×2×3×4×5...×19×20, we'd have a number that is divisible by one through twenty. But it wouldn't be the smallest such number.

Why is that? Well, the reason it's too big is because of the overlap between numbers. We don't have to multiply by 2 if we're going to multiply by 4. We don't have to multiply by 3 if we're going to multiply by 6.

The breakthrough is to multiply just the prime factors. We don't need 6 because we'll already have 2 and 3. We don't need 9 if we multiply two 3's.

The question is, how many of each prime factor do we need? How many 2's? How many 3's? The answer: we need enough to cover the numbers up to 20. We'll need up to four 2's because 16 = 24. We don't need five, because no number has five 2's in it. We'll need two 3's to handle 9 and 18. And we'll only need one each of 5, 7, 11, 13, 17, and 19—no number has those more than once.

And with that, we can calculate the answer by hand. We don't even need a program!

24 × 32 × 5 × 7 × 11 × 13 × 17 × 19 = 232,792,560

John Kugelman
  • 349,597
  • 67
  • 533
  • 578
  • This is the approach I used when trying it out. I whipped this up in Python and it ran in 0.00012 seconds. I can't imagine a solution that gets much more efficient. – TheSoundDefense Aug 18 '14 at 18:48
1

Project Euler #5,

Given the prime factors:

1 = 1
2 = 2
3 = 3
4 = 2^2
5 = 5
6 = 2 * 3
7 = 7
8 = 2^3
9 = 3^3
10 = 2 * 5
11 = 11
12 = 2^2 * 3
13 = 13
14 = 2 * 7
15 = 3 * 5
16 = 2^4
17 = 17
18 = 2 * 3^2
19 = 19
20 = 2^2 * 5

Then this problem is really: Product((a prime factor)**(the largest multiple of this common factor), all common factors)

lcm(1,2,3,4,5,6,7,8,9,10) = 2^13 * 3^2 * 5^1 * 7^1 = 2520
lcm(1,...,20) = 2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19

By the way, it appears you aren't the first person to fall into the brute force trap: Project Euler 5 in Python - How can I optimize my solution?

Now figure out how to do this in code.

Community
  • 1
  • 1
IceArdor
  • 1,961
  • 19
  • 20
0

There are obvious fixes that you can do to speed things up such as:

  • starting at the very lowest possible number, (hint nothing below 20 is divisible by 20 this will skip 18 steps),
  • stepping by 2 will half the work by skipping odd numbers but
  • your number must be divisible by all your factors stepping by your largest divisor, (20 this will reduce your work by 95%),

  • ets.

    but a better approach is to consider that all possible solutions will be a product of some or all of your factors - so you could just check the possible products of 3-19 of your factors, keep those that meet the requirements and then return the lowest. You can further remove those factors that are present in higher factors, e.g. 2, 4 & 5 are already in 20, 3 in 9, etc.

Steve Barnes
  • 27,618
  • 6
  • 63
  • 73