All Divisors of Number - Visualization

Problem Statement❯

Given a positive integer n, your task is to find all of its divisors.

A divisor of a number n is any number that divides n completely (i.e., leaves no remainder).

Return the list of all such numbers in ascending order.

Examples❯

n Output Description
1 [1] 1 is the smallest positive integer; it divides itself only.
6 [1, 2, 3, 6] 6 has divisors: 1, 2, 3, and 6.
12 [1, 2, 3, 4, 6, 12] Divisors include all numbers that divide 12 with no remainder.
17 [1, 17] 17 is a prime number; only divisible by 1 and itself.
100 [1, 2, 4, 5, 10, 20, 25, 50, 100] Multiple divisors due to factors like 2, 5, and their powers.
0 [] Zero has no valid positive divisors in this context.
"" [] Empty input is treated as invalid or zero; returns empty result.

Solution❯

Understanding the Problem

We are given a positive integer n, and we need to find all of its divisors.

A divisor is any number that divides n exactly, meaning the remainder is zero.

For example, if n = 12, the numbers 1, 2, 3, 4, 6, 12 are all divisors because they divide 12 without leaving a remainder.

Our goal is to return all such numbers in ascending order.

Step-by-Step Solution with Example

Step 1: Initialize an empty list

We start by creating an empty list to collect the divisors.

Step 2: Loop from 1 to √n

Why √n? Because if i is a divisor of n, then n / i is also a divisor.

For example, for n = 12:

  • 1 divides 12 → pair is (1, 12)
  • 2 divides 12 → pair is (2, 6)
  • 3 divides 12 → pair is (3, 4)

After i = 3, any new i would result in a repeated or reversed pair.

Step 3: Check if i divides n

Inside the loop, check if n % i == 0.

If it does, add i to the list.

Also, add n / i as long as it is different from i (to avoid adding square roots twice).

Step 4: Sort the list

Since we are adding pairs in no particular order, sort the final list of divisors before returning.

Let’s go through an example: n = 12

Initialize divisors = []

Loop i from 1 to √12 (which is about 3.46, so go up to 3)

  • i = 1 → 12 % 1 == 0 → add 1 and 12
  • i = 2 → 12 % 2 == 0 → add 2 and 6
  • i = 3 → 12 % 3 == 0 → add 3 and 4

Now we have: [1, 12, 2, 6, 3, 4]

After sorting: [1, 2, 3, 4, 6, 12]

Edge Cases

  • n = 1: The only divisor is 1.
  • n is a prime number (e.g., 7): The divisors will be only 1 and n itself.
  • n is a perfect square (e.g., 36): Be careful not to add the square root twice. For example, 6 * 6 = 36, so we only add 6 once.

Final Thoughts

This method is efficient because we reduce the number of iterations from n to about √n.

It works for all positive integers and ensures correct results even when n is very large.

Sorting at the end guarantees the result is in ascending order, as required.

This approach is both beginner-friendly and optimal for number theory-related problems in competitive programming.

Algorithm Steps❯

  1. Initialize an empty list to store divisors.
  2. Iterate from 1 to sqrt(n).
  3. If i divides n (i.e., n % i == 0):
    • Add i to the list.
    • If i != n/i, also add n/i to the list.
  4. Sort the list of divisors before returning.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int cmpfunc(const void* a, const void* b) {
    int x = *(const int*)a;
    int y = *(const int*)b;
    return (x - y);
}

int main() {
    int n = 36;  // Example number
    int maxDivisors = 1000;
    int divisors[maxDivisors];
    int count = 0;
    int sqrtN = (int)sqrt(n);

    for (int i = 1; i <= sqrtN; i++) {
        if (n % i == 0) {
            divisors[count++] = i;
            if (i != n / i) {
                divisors[count++] = n / i;
            }
        }
    }

    qsort(divisors, count, sizeof(int), cmpfunc);

    printf("Divisors of %d: ", n);
    for (int i = 0; i < count; i++) {
        printf("%d ", divisors[i]);
    }
    printf("\n");
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(√n)In the best case, all divisors come in pairs (i, n/i), and the loop only runs up to √n. This ensures only √n iterations, even if n is a perfect square.
Average CaseO(√n)On average, the loop runs from 1 to √n and checks each number to see if it divides n. Each valid divisor may add up to two numbers to the list (i and n/i), but the loop count is still √n.
Worst CaseO(√n)Even if n is a large prime or perfect square, the number of iterations is limited to √n, making this approach efficient for all input sizes.

Space Complexity❯

O(√n)

Explanation: In the worst case, we could collect up to 2 × √n divisors before sorting, especially if n has many small factors. Additional space is used for the result list, which grows with the number of divisors.

Mallikarjuna Mallisetty, author
About the author

Mallikarjuna Mallisetty

General programming

Mallikarjuna shares practical programming tutorials and foundational concepts designed to help developers learn by building and experimenting.

View LinkedIn profile ↗