Writing Better Code 1

The number 28 has 6 divisors:

1,2,4,7,14,28

The number 5 only has 2 divisors:

1,5

Write a program to find all the divisors of a number.

The mod operator is useful here. Remember that the mod operator gives the remainder when two numbers are divided, so

28 % 14 = 0 
28 % 5  = 3

We can use the mod function to write code as follows

def divisors(n):
    divs = []
    for i in range(1,n+1):
    if n%i == 0:
        divs.append(i)
    return divs

print(divisors(28))

The above code is inefficient. To find the divisors of 28, you have to go through the for loop 28 times. To find the divisors of n, we have to go through the for loop n times. We say the code has time complexity O(n).

Try running the code to find the divisors of a large number such as 1347663998. You’ll notice it takes a long time to find the answer. We need a way to make the code more efficient.

You should notice that the divisors come in pairs. (1,28, 2,14 4,7). This suggests a way of saving loops. Rather than looking at all the numbers, we could look at just half of them.

import math

def divisors(n):
    divs = []
    for i in range(1,int(n/2)):
    if n%i == 0:
        divs.append(i)
        divs.append(int(n/i))
    return divs

print(divisors(28))

That seems better, but testing we get repeated divisors

[1, 28, 2, 14, 4, 7, 7, 4]

Thinking about it further we see that we only need to count as far as the square root of n (because root n * root n = n)

import math

def divisors(n):
    divs = []
    for i in range(1,int(math.sqrt(n))):
    if n%i == 0:
        divs.append(i)
        divs.append(int(n/i))
    return divs

print(divisors(28))

There’s still a problem though.

What about divisors of 9?

Run the above code with divisors(9) and you just get

[1, 9]

Isn’t 3 a divisor of 9? The problem lies in our range. We’re counting up to one less then root 9. Let’s tweak the code to take this case into account.

import math

def divisors(n):
    divs = []
    for i in range(1, int(math.sqrt(n))):
    if n%i == 0:
        divs.append(i)
        divs.append(int(n/i))
    if math.sqrt(n).is_integer():
        divs.append(int(math.sqrt(n)))
    return divs

print(divisors(9))

We’ve now got working code that runs a lot faster than the original code.

There are a couple of further tweaks we can make. 

Firstly, all numbers are divisible by 1 and themselves, so we can just append them without checking.

Odd numbers are never divisible by even numbers.  So, if n is odd, we only need to check if n is divisible by 3, 5, 7 …

If n is even we need to check all numbers from 2 onwards.

import math

def divisors(n):
    divs = []
    step = 1
    start = 2
    if n%2 == 1:
        step = 2
        start = 3
    for i in range(start, int(math.sqrt(n)), step):
        if n%i == 0:
            divs.append(i)
            divs.append(int(n/i))
    if math.sqrt(n).is_integer():
        divs.append(int(math.sqrt(n)))
    divs.append(1)
    divs.append(n)
    return divs

One last thing. In the new code the following calculation appears three times: math.sqrt(n)

It takes the computer a lot longer to work out square roots than to do other calculations. Now, a good compiler should notice this. It will perform optimisation on your code and will store repeated calculations to stop them having to be worked out over and over again.

However, it might be more elegant to adjust your code as follows.  I’ve also added a line to sort the divisors into order.

import math

def divisors(n):
    divs = []
    rootn = math.sqrt(n)
    step = 1
    start = 2
    if n%2 == 1:
        step = 2
        start = 3
    for i in range(start, int(rootn), step):
        if n%i == 0:
            divs.append(i)
            divs.append(int(n/i))
    if rootn.is_integer():
        divs.append(int(rootn))
    divs.append(1)
    divs.append(n)
    divs.sort()
    return divs