CODEWITHSUNDEEP
pythonmathdivide
c3ntury
c3ntury

Reputation: 73

Optimising code to find the lowest number divisible by all integers between 1-20

I'm currently trying to problem solve to the question 'What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?'

So far I've coded something up that seems to work, but takes a very long time. Furthermore, I'm having to huge amounts of 'and' statements within an if, which doesn't seem awfully efficient nor professional.

What can I do to optimise this code and make it tidier perhaps?

number = 1
result = 0

def divide(candidate):
    if candidate % 2 == 0 and candidate % 3 == 0 and candidate % 4 == 0 and candidate % 5 == 0 and candidate % 6 == 0 and candidate % 7 == 0 and candidate % 8 == 0 and candidate % 9 == 0 and candidate % 10 == 0 and candidate % 11 == 0 and candidate % 12 == 0 and candidate % 13 == 0 and candidate % 14 == 0 and candidate % 15 == 0 and candidate % 16 == 0 and candidate % 17 == 0 and candidate % 18 == 0 and candidate % 19 == 0 and candidate % 20 == 0:
        global result
        result = 1
        return 1

    else:
       global number
        result = 0
        number = number + 1
        return 0

while result == 0:
divide(number)

print "The lowest number divisible by all integers between 1-20 is:", number

Just to clarify, this isn't homework, I'm self-teaching myself Python and am attempting some ProjectEuler problems as part of this.

Upvotes: 1

Views: 5414

Answers (4)

Thiem Nguyen
Thiem Nguyen

Reputation: 6365

A very simple but quite efficient here is to use only prime numbers and their powers. Why do you have to consider their multiply, right? Reduce your "and" conditions to only 4,9,16,5,7,11,13,17,19

Upvotes: 0

Sven Marnach
Sven Marnach

Reputation: 602745

Your problem can be easiliy solved without the help of a computer, so an optimised version would simply print the answer. It's a bit hard to tell what amount of optimisation you would consider admissible.

Here's how to solve this question without a computer. The smallest number divisible by all numbers from 1 to 20 must be divisible by all prime powers occuring among these numbers. And, on the other hand, if we have a number divisible by all prime powers in this range, it will be divisble by all numbers from 1 to 20. Since prime powers with different bases are coprime, the product of all the highest prime powers for each prime in this range will be the answer. So here is the optimised code:

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

Upvotes: 9

Matt
Matt

Reputation: 45

If it was me I'd just try to 'mod' (%) the prime numbers. I wouldn't use every number from 1 to 20.

Upvotes: 0

jsmith
jsmith

Reputation: 575

You can start by eliminating numbers that are factors of previous numbers. All numbers divisible by 4 are divisible by 2. All numbers divisible by 10 are divisible by 5, All numbers divisible by 9 are divisible by 3, etc.

Upvotes: 2

Related Questions