Table of Contents

## Problem Formulation

Given an integer number `n`

.

Get all divisors `c`

of the number `n`

so that `c * i = n`

for another integer `i`

. The desired output format is a list of integers (divisors).

Here are a couple of examples:

n = 10 # Output: [1, 2, 5, 10] n = 13 # Output: [1, 13] n = 24 # Output: [1, 2, 3, 4, 6, 8, 12]

## Method 1: Naive Approach

Integer `i`

is a divisor of `n`

if `n modulo i`

is zero.

We use this observation in the function `divisors()`

. We create an initially empty list `result`

and check for every integer number `i`

between 0 and `n/2`

whether this number is a divisor of `n`

. If it is, we append it to the list.

The following Python code accomplishes this:

def divisors(n): result = [] for i in range(1, n//2 + 1): if n % i == 0: result.append(i) result.append(n) return result print(divisors(24)) # [1, 2, 3, 4, 6, 8, 12, 24]

This approach is not very efficient because we traverse every single number from 0 to `n/2`

. If the number n becomes large such as `n=1000000`

, we need to check every number `i=0, i=1, i=2, i=3, ..., i=500000`

.

**Runtime complexity:** The runtime complexity of calculating the divisors of number* n* is *O(n)* using this approach assuming the modulo operation can be performed in one step.

Can we do better? Yes!

## Method 2: Reducing the Number of Loop Iterations

We use two observations to reduce the number of loop iterations of the “naive algorithm”.

**Observation 1:** If number `i`

is a divisor of `n`

, number `j = n/i`

must be an integer and a divisor of `n`

as well because `i * n/i = n`

. This means that each time we find a divisor `i`

, we can also add the divisor `n/i`

to the list of divisors.

**Observation 2:** For a pair of `n`

-divisors `(i, j)`

, one of them must be smaller than or equal to the square root of `n`

. The reason is simple: if both were larger than the square root, the multiplication `i * j `

would be larger than `n`

for sure because `root(n) * root(n) == n`

. Thus, we can traverse the potential divisors from `i=0`

to `i=root(n)`

and be sure to have found all divisors. This saves us all iterations from `i=root(n)`

to `i=n//2`

.

Here’s the simple tweak with significant performance benefits:

def divisors(n): result = set() for i in range(1, int(n**0.5)+1): if n % i == 0: result.add(i) result.add(n//i) return list(result) print(divisors(24)) # [1, 2, 3, 4, 6, 8, 12, 24]

This code iterates only from 0 to the square root of the number `n`

. If we find a divisor `i`

, we also add `n//i`

which is the other factor and a divisor of `n`

as well.

**Runtime complexity:** The runtime complexity of calculating the divisors of number* n* is *O(n^0.5)* using this approach assuming the modulo operation is counted as one step.

## Where to Go From Here?

Enough theory, let’s get some practice!

To become successful in coding, you need to get out there and solve real problems for real people. That’s how you can become a six-figure earner easily. And that’s how you polish the skills you really need in practice. After all, what’s the use of learning theory that nobody ever needs?

**Practice projects is how you sharpen your saw in coding!**

Do you want to become a code master by focusing on practical code projects that actually earn you money and solve problems for people?

Then become a Python freelance developer! It’s the best way of approaching the task of improving your Python skills—even if you are a complete beginner.

Join my free webinar “How to Build Your High-Income Skill Python” and watch how I grew my coding business online and how you can, too—from the comfort of your own home.

While working as a researcher in distributed systems, Dr. Christian Mayer found his love for teaching computer science students.

To help students reach higher levels of Python success, he founded the programming education website Finxter.com. He’s author of the popular programming book Python One-Liners (NoStarch 2020), coauthor of the Coffee Break Python series of self-published books, computer science enthusiast, freelancer, and owner of one of the top 10 largest Python blogs worldwide.

His passions are writing, reading, and coding. But his greatest passion is to serve aspiring coders through Finxter and help them to boost their skills. You can join his free email academy here.