Python Program to Print Divisors/Factors of an Integer

Hi everyone! In this article, we’ll explain the Python program to print divisors/factors of an integer. Helping you understand better via examples, approach, code, dry run, edge cases & time and space complexity.

Examples

Example 1:

  Input: x = 10
  Output: 1 2 5 10

Example 2:

  Input: x = 20
  Output: 1 2 4 5 10 20

Example 3:

  Input: x = 7
  Output: 1 7

1.BRUTE FORCE SOLUTION of Python Program to Print Divisors/Factors of an Integer

Problem Statement:

Objective: We need to find all the factors of a given integer.

Expected Input and Output:

• Input: An integer “num”
• Output: A list of integers that are factors of “num”

Intuition and Approach:

Intuition: A factor of a number “num” is any integer “i” such that num % i == 0. By iterating through all integers from 1 to “num”, we can check each integer to see if it divides “num” without a remainder and collect all such integers.

Approach:

1. Initialize an empty list to store the factors
2. Loop through all integers from 1 to “num” inclusive
3. For each integer “i”, check if num % i == 0
4. If the condition is true, add “i” to the list of factors
5. Return the list of factors after the loop completes

Code:

from typing import List

def factors(num: int) -> List[int]:
    factors = []
    for i in range(1, num + 1):
        if num % i == 0:
            factors.append(i)

    return factors

1. Initialize List: An empty list factors is initialized to store the factors of “num”.
2. Loop Through Integers: A for loop iterates from 1 to “num” inclusive.
3. Check Divisibility: For each integer “i”, check if it divides “num” without leaving a remainder using num % i == 0.
4. Add Factor: If “i” is a factor, append it to the factors list.
5. Return List: After the loop completes, return the factors list containing all the factors of “num”.

Dry Run:

Let’s walk through a step-by-step execution with a sample input explained through images.

Potential Edge Cases:

1. num = 1: The function should return [1] because 1 is a factor of itself.
2. num = 0: By mathematical convention, every integer is a factor of 0, but usually, the function might return an empty list or handle it specially since 0 % any number is 0.
3. num < 0: The function currently doesn’t handle negative numbers. If negative numbers are considered, the factors should be the absolute values.

Handling Edge Cases:

• For num = 1, the function correctly returns [1].
• For num = 0, the function currently returns [] as it doesn’t explicitly handle 0.
• For negative numbers, the function should handle the absolute value or reject negative inputs depending on the requirements.

Time and Space Complexity:

Time Complexity: The time complexity is “O(n)” because the function iterates from 1 to “num” and performs a modulo operation for each iteration.

Space Complexity: The space complexity is “O(k)”, where “k” is the number of factors of “num”, as it stores the factors in a list.

Also read: Python Program to Check Armstrong Number.

2.BETTER SOLUTION of Python Program to Print Divisors or Factors of an Integer

Problem Statement:

Objective: We need to find all the factors of a given integer.

Expected Input and Output:

• Input: An integer “num”
• Output: A list of integers that are factors of “num”

Intuition and Approach:

Intuition: A factor of a number “num” is any integer “i” such that num % i == 0. To optimize the search, we only need to check integers up to num // 2 because any number larger than num // 2 (except “num” itself) cannot be a factor.

Approach:

1. Initialize an empty list to store the factors
2. Loop through all integers from 1 to num // 2 inclusive
3. For each integer “i”, check if num % i == 0
4. If the condition is true, add “i” to the list of factors
5. After the loop, add “num” itself to the list since it is always a factor
6. Return the list of factors

Code:

from typing import List

def factors(num: int) -> List[int]:
    factors = []
    for i in range(1, num // 2 + 1):
        if num % i == 0:
            factors.append(i)
    factors.append(num)
    return factors

1. Initialize List: An empty list factors is initialized to store the factors of “num”.
2. Loop Through Integers: A for loop iterates from 1 to num // 2 inclusive.
3. Check Divisibility: For each integer “i”, check if it divides “num” without leaving a remainder using num % i == 0.
4. Add Factor: If “i” is a factor, append it to the factors list.
5. Add the Number Itself: After the loop, add “num” itself to the list of factors.
6. Return List: Return the factors list containing all the factors of num”.

Dry Run:

Let’s walk through a step-by-step execution with a sample input explained through images.

Potential Edge Cases:

1. num = 1: The function should return [1] because 1 is a factor of itself.
2. num = 0: By mathematical convention, every integer is a factor of 0, but usually, the function might return an empty list or handle it specially since 0 % any number is 0.
3. num < 0: The function currently doesn’t handle negative numbers. If negative numbers are considered, the factors should be the absolute values.

Handling Edge Cases:

• For num = 1, the function correctly returns [1].
• For num = 0, the function currently returns [] as it doesn’t explicitly handle 0.
• For negative numbers, the function should handle the absolute value or reject negative inputs depending on the requirements.

Time and Space Complexity:

Time Complexity: The time complexity is “O(n/2)” or “O(n)”, where “n” is the input number. This is because the function iterates from 1 to num // 2 and performs a modulo operation for each iteration.

Space Complexity: The space complexity is “O(k)”, where “k” is the number of factors of “num”, as it stores the factors in a list.

Also read: Palindrome Number Program in Python | Leetcode #9.

3.OPTIMAL SOLUTION of Python Program to Print Divisors or Factors of an Integer

Problem Statement:

Objective: We need to find all the factors of a given integer.

Expected Input and Output:

• Input: An integer “num”.
• Output: A list of integers that are factors of “num”.

Intuition and Approach:

Intuition: A factor of a number “num” is any integer “i” such that num % i == 0. Instead of iterating through all numbers up to “num”, we can optimize the search by only iterating up to the square root of “num”. For each divisor “i” found in this range, both “i” and num // i are factors of “num”.

Approach:

1. Initialize an empty list to store the factors
2. Loop through all integers from 1 to the square root of “num” inclusive
3. For each integer “i”, check if num % i == 0
4. If “i” is a factor, add “i” to the list
5. If num // i is not equal to “i”, add num // i to the list to avoid duplicates
6. Optionally, sort the list of factors before returning it

Code:

from typing import List
from math import sqrt


def factors(num: int) -> List[int]:
    factors = []
    for i in range(1, int(sqrt(num)) + 1):
        if num % i == 0:
            factors.append(i)
            if num // i != i:
                factors.append(num // i)
    factors.sort()  # Do this only if you want in sorted order
    return factors

1. Import Required Modules: Import the “List” type from “typing” and the “sqrt” function from “math”.
2. Initialize List: An empty list factors is initialized to store the factors of “num”.
3. Loop Through Integers: A for loop iterates from 1 to the integer value of the square root of “num” inclusive.
4. Check Divisibility: For each integer “i”, check if it divides “num” without leaving a remainder using num % i == 0.
5. Add Factor: If “i” is a factor, append it to the factors list.
6. Add Corresponding Factor: If num // i is not equal to “i”, append num // i to the factors list to avoid duplicates.
7. Sort Factors: Sort the factors list if sorted order is desired.
8. Return List: Return the factors list containing all the factors of “num”.

Dry Run:

Let’s walk through a step-by-step execution with a sample input explained through images.

Potential Edge Cases:

1. num = 1: The function should return [1] because 1 is a factor of itself.
2. num = 0: By mathematical convention, every integer is a factor of 0, but usually, the function might return an empty list or handle it specially since 0 % any number is 0.
3. num < 0: The function currently doesn’t handle negative numbers. If negative numbers are considered, the factors should be the absolute values.

Handling Edge Cases:

• For num = 1, the function correctly returns [1].
• For num = 0, the function currently returns [] as it doesn’t explicitly handle 0.
• For negative numbers, the function should handle the absolute value or reject negative inputs depending on the requirements.

Time and Space Complexity:

Time Complexity: The time complexity is “O(n)” because the function iterates from 1 to the square root of “num” and performs a modulo operation for each iteration.

Space Complexity: The space complexity is “O(k)”, where “k” is the number of factors of “num”, as it stores the factors in a list.