As part of Nick Russo’s DevAsc study plan, he recommends doing a few Python challenges to check your existing knowledge of Python. One of these is the Divisors challenge. The goal of of this exercise is to take a number, such as 12, and then find all the divisors, that is the numbers that you can divide 12 with and have no remainder. This would 1, 2, 3, 4, 6, and finally 12 itself.

Now, solving this doesn’t take a lot of code. However, I decided that gold plating is allowed in my studies of code. That is, I would rather practice writing functions from the get go rather than just quickly moving from exercises.

To find divisors, we need a little basic math. We can use the Modulo operation to find the reminder of a division. For example, if you divide 5 by 2, the remainder is 1. We call this 5 modulo 2. Because there is a remainder of 1, this means that 2 is not a divisor for 5. If we however use 9 and 3 instead, with 9 modulo 3, the remainder is 0. This means that 3 is a divisor for 9. We then know that the remainder should be 0 for all divisors and we can easily check this with the modulo operation.

I decided to divide my code into three functions:

- get_number
- create_list
- check_divisor

First, it’s good practice to describe what your program does with a docstring:

"""Program to check all divisors of a positive integer"""

Our program will look for all divisors for positive integers.

The first step to finding a divisor, is to ask the user for what number to check. We can ask the user to input a number using the `input()`

function in Python.

number = input("Please enter a positive integer: ")

It’s important to note that this function returns a string. We need a number, more specifically an integer. Luckily, we can use the `int()`

function to get an integer from the string specified. We will call this variable `number_int`

.

Like I said, I wanted to create a function out of this code:

def get_number(): """Get a number from user, convert to integer, and return the value""" # Get number, this will be a string number = input("Please enter a positive integer: ") # Convert string to an integer number_int = int(number) # Return the number return number_int

Notice that the function returns `number_int`

and that this function doesn’t require any arguments. When I first tried my complete solution, I had an error saying something about `number_int`

not being defined. What I hadn’t realized, was that even though I am returning `number_int`

in my function, this variable is only known within the function. It does not have global scope. I wanted to take this value and feed it into the next function. We’ll get back to this later.

Our next goal is to create a list that contains all possible divisors. In Python, there is a function called `range()`

that we can use to create ranges of values. To find all divisors, we want to create a list where 1 is the first number and where the last number is the number that the user input, namely `number_int`

. When using the `range()`

function, the first argument we give is the starting number. The second argument we give, is the ending number. However, ending number actually means that the range is from starting number to ending number – 1. Meaning that if we use `range(1, 10)`

, the range would be from 1 to 9.

One error I did at this point was thinking I could create a list like this:

>>> mylist = range(1, 10) >>> print(mylist) range(1, 10)

However, as you see, this just created a list containing the range, not the numbers themself. What we need to do is to combine this with the `list()`

function.

>>> mylist = list(range(1, 10)) >>> print(mylist) [1, 2, 3, 4, 5, 6, 7, 8, 9]

Now we have an actual list.

Great, now let’s turn this into a function. We want to send the argument `number_int`

into the function. When creating the list, the range will be from 1 to `number_int`

+ 1. Why do we need to add 1 to number_int? Because otherwise the list will not be complete because the `range()`

function creates a range where the range ends one number before the ending number input.

def create_list(number_int): """Create list consisting of all numbers from zero to user-specified number, to find divisors""" # Create list using range, user number plus 1 is end number mylist = list(range(1, (number_int + 1))) # Return the list return mylist

We return a list called `mylist`

. One mistake I made here was first calling the list I was creating `list`

. Don’t name your variables to something that exists within Python itself, such as function names, you may end up with code not running.

Now for the code that actually looks for divisors. What we are trying to achieve is this:

- Create an empty list containing divisors
- Iterate through all numbers in mylist
- Check if we have a divisor with modulo function
- If we have a match, add it to the list
- Print all the divisors

Creating an empty list is as easy as this:

divisors = []

We then have the code looking for divisors:

for number in mylist: # Check if modulo is 0, then divisor is found if (mylist[-1] % number == 0): # When divisor found, add to list divisors.append(number)

We iterate through all the numbers in mylist using the iterator `number`

. To see if we have a divisor, we have in if statement with `(mylist[-1] % number == 0)`

. What does `mylist[-1]`

mean? It’s the last number in our list, the number that the user originally input. To use the modulo fuction in Python, we use the `%`

operator. If the result is == 0, then we have a divisor.

If a divisor is found, we add it to the list called divisors with the `append()`

function.

We also want the function to print all the divisors. This is done below:

for divisor in divisors: print(divisor)

All the divisors are in the `divisors`

list. We iterate using `divisor`

and then simply print them one by one.

We now have three functions, but our code doesn’t really do anything. We need to actually call the functions. This is done below:

if __name__ == "__main__": number_int = get_number() mylist = create_list(number_int) check_divisor(mylist)

The first if statement just checks that if dunder `name`

is dunder `main`

, the code is run, that is if it’s run standalone and not imported as a module.

Like I mentioned before, variables are local to functions. That’s why I need to use `number_int`

globally. I get this value by calling `get_number()`

. Then this number, an integer, is fed into `create_list`

, as an argument, to create our list of potential divisors. Finally, we take the result of this function in the form of `mylist`

, send it through `check_divisor`

and get our divisors printed to us. Neat! This is what it looks like:

daniel@devasc:~/DevAsc$ python3 divisors.py Please enter a positive integer: 48 1 2 3 4 6 8 12 16 24 48 daniel@devasc:~/DevAsc$

Finally, here’s the entire code if you want to run it for yourself:

"""Program to check all divisors of a positive integer""" def get_number(): """Get a number from user, convert to integer, and return the value""" # Get number, this will be a string number = input("Please enter a positive integer: ") # Convert string to an integer number_int = int(number) # Return the number return number_int def create_list(number_int): """Create list consisting of all numbers from zero to user-specified number, to find divisors""" # Create list using range, user number plus 1 is end number mylist = list(range(1, (number_int + 1))) # Return the list return mylist def check_divisor(mylist): """Take a list and check for all divisors""" # Create empty list to store divisors divisors = [] # Loop through the list for number in mylist: # Check if modulo is 0, then divisor is found if (mylist[-1] % number == 0): # When divisor found, add to list divisors.append(number) # Print all divisors for divisor in divisors: print(divisor) # Run code if not imported as module if __name__ == "__main__": number_int = get_number() mylist = create_list(number_int) check_divisor(mylist)

I have also added the code to Github.

I hope this post was helpful. I certainly learned a lot by writing it.

Pingback:DevAsc – Python Palindrome Challenge – Daniels Networking Blog

Hi.

First of all, this code is very memory hungry. You`re creating the list with every number between 1 and target. Try with a big one, it simply won`t work.

Please enter a positive integer: 999999999

Traceback (most recent call last):

…

MemoryError

Second, this code is very slow. Try with a working, but big number.

My PC needs almost 29 seconds to calculate divisors for 100 000 000 with your program.

Cheers 🙂

My version of function:

def check_divisor(targetNumber):

“””Check for all divisors”””

# Create empty list to store divisors

divisors = list()

for x in range(1, int(math.sqrt(targetNumber))+1): # Should check till sqrt(x)

if not targetNumber%x:

divisors.append(x)

if targetNumber/x != x: # If target is not a square, add second divisor

divisors.append(int(targetNumber/x))

divisors.sort() # To get a sorted list

for x in divisors:

print(x)

It stores only divisors it has found and it works quite fast.

0.23 seconds to find all divisors of 1 000 000 000 000

Cool! Thanks!