-3
\$\begingroup\$

I have seen multiple questions on this problem but none seem to answer my specific question.

To start, the basic question is asking to find the smallest number that is divisible by numbers 1 to 20.

I have written some code that has solved the problem but the runtime is exceptionally too long for my liking. I guess I don't know enough about math the truly optimize my solution. I understand that iterating in increments of 1 is not the fastest, but I cant think of any other way.

def smallest_divisible(range_max):
    divisors = list(range(2,range_max+1,1)) #We ignore 1 because 1 is 
                                            #divisible by everything
    x = 1
    while True:
        x += 1
        check = divisible(x, divisors)
        if check: return x


def divisible(n, lst):
    #Pass a number to compare to a list to see if the number 
    #is divisible by all elements in list
    return all(map(lambda y: n%y == 0, lst))

\$\endgroup\$
  • 1
    \$\begingroup\$ You can do some pretty basic optimization by starting with 40 and increment by 20, since the answer must be divisible by 20. Secondly, you can greatly narrow down your range as well. Start with 19 (since you already know it's divisible by 20), and work backwards, checking all primes and removing any lower number which you have already checked a multiple of (example: you don't need to check if it's divisible by 3 if you've already checked if it is divisible by 18, since 18 is a multiple of 3). I think the correct range to check would be 19, 18, 17, 16, 15, 14, 13, 12, 11. \$\endgroup\$ – Bodacious Aug 13 at 21:16
  • \$\begingroup\$ To be clear, there is a much better way, and a quick Google search should help ;) \$\endgroup\$ – Bodacious Aug 13 at 21:25
  • \$\begingroup\$ @Bodacious That's roughly the review I got when I solved this :D The good, old try-the-problem-backwards review. \$\endgroup\$ – Hosch250 Aug 13 at 21:30
  • 1
    \$\begingroup\$ Welcome to CodeReview! it doesn't feel like you are asking for a review of your code though, it feels more like you are asking for an algorithm to solve a problem. The Users of CodeReview might be able to review the code that you have written, but will almost certainly steer away from giving out solutions to problems. \$\endgroup\$ – Malachi Aug 14 at 1:02
  • 1
    \$\begingroup\$ “I have seen multiple questions on this problem but none seem to answer my specific question.” – The first 3 search results for [python] project Euler #5 on this site all provide good information, and better algorithms than yours. \$\endgroup\$ – Martin R Aug 14 at 11:19
0
\$\begingroup\$
    divisors = list(range(2,range_max+1,1)) #We ignore 1 because 1 is 
                                            #divisible by everything

The comment is wrong. 0 is divisible by everything. 1 is divisible into everything.


    x = 1
    while True:
        x += 1
        check = divisible(x, divisors)
        if check: return x

I think it would be more Pythonic to use itertools.count(2). In fact, I'd tend towards the one-liner

    return next(iter(x for x in count(2) if divisible(x, divisors)))

def divisible(n, lst):
    #Pass a number to compare to a list to see if the number 
    #is divisible by all elements in list
    return all(map(lambda y: n%y == 0, lst))

Again, I think the more Pythonic approach is a comprehension:

    return all(n%y == 0 for y in lst)

And I'd rename lst to divisors. The meaning of the value is more important than its type.


I have seen multiple questions on this problem but none seem to answer my specific question.

. I understand that iterating in increments of 1 is not the fastest, but I cant think of any other way.

I've also seen multiple questions on this problem, and as I recall, all of them answered that question. So rather than repeat them all, what I'll offer is that if you list five questions which don't, I'll list five that do.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.