Find all Divisors of Number in Python

This article explores different Python techniques for finding all the divisors of a given integer. It begins with a straightforward approach using a simple for loop, iterating through potential divisors and checking for remainders. It then delves into optimized methods, such as iterating only up to the square root of the number to improve efficiency.

Additionally, the article covers techniques using list comprehensions and set operations for concise and elegant solutions.

1. Find all the Divisors of a Number in Python using loop

for loop is the most straightforward method for finding all the factors/divisors of a number in Python. We use the modulo operator (%) to check all numbers from 1 to n to see if they divide n without leaving a remainder. 

This approach is simple and works well for small numbers.

Code Example

num = 36
divisors = []
for i in range(1, num + 1):
    if num % i == 0:
        divisors.append(i)
print(f"Divisors of {num}: {divisors}")Code language: Python (python)

Output:

Divisors of 36: [1, 2, 3, 4, 6, 9, 12, 18, 36]Code language: Python (python)

Explanation

• range() function: Generates numbers sequentially from 1 to num + 1, defining the range of numbers to check as potential divisors.
• Modulo operator (%): This operator checks if dividing num by a given number results in no remainder. If num % i == 0, then i is a divisor, and it is added to the list.

2. Using math.sqrt function

math.sqrt() is a function in Python’s math module that returns the square root of a given number. To find all divisors of a number efficiently, we have used the math.sqrt() function to limit the number of iterations. Instead of checking all numbers up to n, you only iterate up to sqrt(n).

For each divisor i found in this range, both i and its complementary divisor (n // i) are included in the list of divisors. This significantly reduces the number of iterations while ensuring all divisors are identified.

For Example,

• Let say, num = 12, divisors = []
• The loop runs from 1 to √12 = 3
• Iteration 1: num % i = 12 % 1 = 0 and 12 // 1 = 12, divisors = [1, 12]
• Iteration 2: num % i = 12 % 2 = 0 and 12 // 2 = 6, divisors = [1, 12, 2, 6]
• Iteration 3: num % i = 12 % 3 = 0 and 12 // 3 = 4, divisors = [1, 12, 2, 6, 3, 4]

Code Example

import math

num = 36
divisors = []

# Iterate from 1 to sqrt(num)
for i in range(1, int(math.sqrt(num)) + 1):
    if num % i == 0:       # If 'i' is a divisor of 'num'
        divisors.append(i) # Add 'i' to the list of divisors
        if i != num // i:
            divisors.append(num // i)  # Add the corresponding divisor
print(f"Divisors of {num}: {divisors}")

# Output:
# Divisors of 36: [1, 36, 2, 18, 3, 12, 4, 9, 6]Code language: Python (python)

Explanation

This method leverages three key elements to find divisors efficiently:

• math.sqrt function: Used to calculate the square root of n, determining the range up to which we need to check for divisors. int() function is used to convert the square root value into a whole number. For example, math.sqrt(12) = 3.4 whereas, int(math.sqrt(12)) = 3
• range() function: Generates numbers from 1 to the square root of n.
• Modulo operator(%): Checks if a number divides n without leaving a remainder.
• Floor division operator (//): The floor division operator (//) in Python divides two numbers and returns a quotient. If i is a divisor, then n // i is also a divisor, and both are included in the list.

3. Using List Comprehension

This method uses list comprehension, a concise way to create lists in Python by iterating over a sequence and applying a condition.

Here, it simplifies the logic of the for loop by iterating through numbers from 1 to num + 1 and directly adding those that divide num without a remainder, i.e., num % i == 0.

Code Example

num = 36
divisors = [i for i in range(1, num + 1) if num % i == 0]
print(f"Divisors of {num}: {divisors}")

# Output:
# Divisors of 36: [1, 2, 3, 4, 6, 9, 12, 18, 36]Code language: Python (python)

Explanation

• range() function: Generates numbers from 1 to num + 1, defining the range of potential divisors to check.
• Modulo operator(%): Used to check if num is divisible by each number in the range. If the result is 0, the number is added to the list of divisors.
• List comprehension: Provides a concise way to create a list of divisors by iterating over the range and applying the condition num % i == 0. Only numbers that divide num without a remainder are included in the list.

4. Using a Generator

In Python, a generator is a special function that yields values one at a time as they are produced instead of returning them all at once.

Here, logic is the same as we have seen in math.sqrt method but a generator function is used to yield divisors one by one, making it more memory-efficient for large numbers as it avoids storing all divisors in memory at once. It is particularly suitable for scenarios with limited memory.

Code Example

def find_divisors_generator(n):
    for i in range(1, int(n**0.5) + 1):  # Loop up to √n
        if n % i == 0:
            yield i
            if i != n // i:
                yield n // i      # Yield the paired divisor

num = 36
divisors = list(find_divisors_generator(num))
print(f"Divisors of {num}: {divisors}")

# Output:
# Divisors of 36: [1, 36, 2, 18, 3, 12, 4, 9, 6]Code language: Python (python)

Explanation

This method uses a generator to yield divisors as they are found. It incorporates:

• range() function: Generates numbers from 1 to the square root of n, defining the range of potential divisors. Square root of n is find out using int(n**0.5)
• Modulo operator (%) & Floor division operator (//): Checks if a number divides n without leaving a remainder. If true, the number and its complementary divisor (n // i) are yielded.
• yield keyword: Produces each divisor one at a time instead of storing all divisors in memory, making the approach highly memory-efficient.

Summary

These methods offer flexibility depending on your use case: simplicity, efficiency, or memory optimization.

Each of these methods provides distinct advantages and has different time and space complexities:

1. Loop Method:
   • Advantage: Simple to understand and implement; works well for small numbers.
   • Time Complexity: O(n) – Iterates through all numbers from 1 to n.
   • Space Complexity: O(d) – Stores all divisors in a list, where d is the number of divisors.
   • Disadvantage: Its not time efficient.
2. math.sqrt function:
   • Advantage: Efficient for larger numbers by reducing iterations significantly.
   • Time Complexity: O(√n) – Iterates up to the square root of n. Its time efficient solution
   • Space Complexity: O(d) – Stores all divisors in a list, where d is the number of divisors.
3. List Comprehension:
   • Advantage: Provides a concise and readable solution.
   • Time Complexity: O(n) – Similar to the for loop method, iterates through all numbers from 1 to n.
   • Space Complexity: O(d) – Stores all divisors in a list, where d is the number of divisors.
   • Disadvantage: Its not time efficient.
4. Generator Method:
   • Advantage: Most memory-efficient as it avoids storing all divisors at once.
   • Time Complexity: O(√n) – Iterates up to the square root of n.
   • Space Complexity: O(1) – Does not store all divisors simultaneously, yielding them one by one.