Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Finding All Divisors

EASYProblemSolveExternal Links

Description

Given a positive integer n, find and return all the divisors of n in ascending order.

A divisor (also called a factor) of an integer n is any positive integer d such that n is perfectly divisible by d — that is, dividing n by d leaves zero remainder (n % d == 0).

For example, the divisors of 12 are 1, 2, 3, 4, 6, and 12 because each of these numbers divides 12 evenly.

Every positive integer n has at least two divisors: 1 (since every number is divisible by 1) and n itself (since every number is divisible by itself). If those are the only two divisors, the number is called a prime number.

Your task is to print all divisors of the given number in increasing order.

Examples

Example 1

Input: n = 20

Output: 1 2 4 5 10 20

Explanation: We check which numbers from 1 to 20 divide 20 evenly:

  • 20 % 1 = 0 ✓ → 1 is a divisor
  • 20 % 2 = 0 ✓ → 2 is a divisor
  • 20 % 3 = 2 ✗ → 3 is NOT a divisor
  • 20 % 4 = 0 ✓ → 4 is a divisor
  • 20 % 5 = 0 ✓ → 5 is a divisor
  • 20 % 10 = 0 ✓ → 10 is a divisor
  • 20 % 20 = 0 ✓ → 20 is a divisor

So the divisors are: 1, 2, 4, 5, 10, 20.

Example 2

Input: n = 21191

Output: 1 21191

Explanation: 21191 is a prime number — it is not divisible by any integer other than 1 and itself. No number from 2 through 21190 divides it evenly, so the only divisors are 1 and 21191.

Example 3

Input: n = 36

Output: 1 2 3 4 6 9 12 18 36

Explanation: 36 is a perfect square (6 × 6 = 36). Notice the divisors come in pairs: (1, 36), (2, 18), (3, 12), (4, 9), (6, 6). Since 6 × 6 = 36, the divisor 6 appears as both halves of the pair, but we list it only once. Total: 9 divisors.

Constraints

  • 1 ≤ n ≤ 10^9

Editorial

Brute Force

Intuition

The simplest way to find all divisors is to follow the definition directly: a divisor d of n is any number where n % d == 0.

So we can check every number from 1 to n, one by one, and ask: "Does this number divide n evenly?" If yes, we add it to our list of divisors.

Think of it like having a collection of n keys and a single lock. You try every key from 1 through n. If a key fits (divides n perfectly), you keep it. Otherwise, you discard it. By the time you have tried all n keys, you have found every divisor.

Step-by-Step Explanation

Let's trace through with n = 20:

Step 1: Start with an empty result list. Set i = 1.

Step 2: Check i = 1. Is 20 % 1 == 0? Yes → add 1 to result. Result: [1].

Step 3: Check i = 2. Is 20 % 2 == 0? Yes → add 2. Result: [1, 2].

Step 4: Check i = 3. Is 20 % 3 == 0? No (remainder = 2) → skip.

Step 5: Check i = 4. Is 20 % 4 == 0? Yes → add 4. Result: [1, 2, 4].

Step 6: Check i = 5. Is 20 % 5 == 0? Yes → add 5. Result: [1, 2, 4, 5].

Step 7: Check i = 6 through i = 9. None divide 20 evenly → skip all.

Step 8: Check i = 10. Is 20 % 10 == 0? Yes → add 10. Result: [1, 2, 4, 5, 10].

Step 9: Check i = 11 through i = 19. None divide 20 evenly → skip all.

Step 10: Check i = 20. Is 20 % 20 == 0? Yes → add 20. Result: [1, 2, 4, 5, 10, 20].

Result: [1, 2, 4, 5, 10, 20] — we checked all 20 numbers from 1 to n.

Brute Force — Checking Every Number from 1 to n — Watch how we iterate through every number from 1 to 20 and check divisibility, collecting divisors along the way.

Algorithm

  1. Initialize an empty list to store divisors
  2. Iterate i from 1 to n (inclusive):
    • If n % i == 0, append i to the divisors list
  3. Return the divisors list (it is already in ascending order since we iterated in order)

Code

#include <iostream>
#include <vector>
using namespace std;

vector<int> allDivisors(int n) {
    vector<int> divisors;
    
    // Check every number from 1 to n
    for (int i = 1; i <= n; i++) {
        if (n % i == 0) {
            divisors.push_back(i);
        }
    }
    
    return divisors;
}

int main() {
    int n = 20;
    vector<int> result = allDivisors(n);
    
    for (int d : result) {
        cout << d << " ";
    }
    // Output: 1 2 4 5 10 20
    
    return 0;
}
def all_divisors(n: int) -> list:
    divisors = []
    
    # Check every number from 1 to n
    for i in range(1, n + 1):
        if n % i == 0:
            divisors.append(i)
    
    return divisors

n = 20
result = all_divisors(n)
print(*result)  # Output: 1 2 4 5 10 20
import java.util.ArrayList;
import java.util.List;

public class AllDivisors {
    public static List<Integer> allDivisors(int n) {
        List<Integer> divisors = new ArrayList<>();
        
        // Check every number from 1 to n
        for (int i = 1; i <= n; i++) {
            if (n % i == 0) {
                divisors.add(i);
            }
        }
        
        return divisors;
    }
    
    public static void main(String[] args) {
        int n = 20;
        List<Integer> result = allDivisors(n);
        
        for (int d : result) {
            System.out.print(d + " ");
        }
        // Output: 1 2 4 5 10 20
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate from 1 to n, performing one modulo operation per iteration. The total number of iterations is exactly n. For n = 10^9, that is one billion iterations — which takes several seconds and will likely exceed time limits.

Space Complexity: O(1)

Excluding the output list, we only use a loop variable. The space used does not grow with n (the output list is required regardless of approach).

Why This Approach Is Not Efficient

The brute force iterates from 1 to n, performing n modulo operations. With the constraint n ≤ 10^9, that means up to one billion iterations — this will take several seconds and almost certainly exceed typical time limits of 1-2 seconds.

But look at the pattern we discovered in Example 3: the divisors of 36 come in pairs: (1, 36), (2, 18), (3, 12), (4, 9), (6, 6). In each pair (d₁, d₂), we have d₁ × d₂ = 36, and importantly, d₁ ≤ √36 = 6 while d₂ ≥ √36 = 6.

This means: for every divisor d ≤ √n, there is a corresponding divisor n/d ≥ √n. We do not need to check numbers beyond √n — once we find d, we automatically know n/d is also a divisor.

Instead of checking all numbers from 1 to n (a billion iterations), we only need to check from 1 to √n. For n = 10^9, √n ≈ 31,623 — roughly 31,000 iterations instead of 1,000,000,000. That is a reduction by a factor of over 30,000!

Optimal Approach - Divisor Pairing with √n Iteration

Intuition

The key mathematical insight is that divisors always come in pairs.

If d is a divisor of n, then n/d is also a divisor of n. For example, if 4 divides 20 (giving quotient 5), then 5 also divides 20 (giving quotient 4). The pair is (4, 5), and 4 × 5 = 20.

In every such pair (d, n/d), the smaller divisor d is always ≤ √n, and the larger divisor n/d is always ≥ √n. Here is why: if both d and n/d were greater than √n, their product d × (n/d) = n would be greater than √n × √n = n, which is a contradiction.

So we only need to iterate from 1 to √n:

  • For each i that divides n, we get two divisors for the price of one: i and n/i
  • Special case: when i = √n (i.e., n is a perfect square), both divisors are the same, so we add it only once

Think of it like a matching game. Divisors come in pairs that "mirror" around √n. By only looking at the smaller half of each pair, we automatically discover the larger half. One sweep up to √n finds all divisors.

To return divisors in sorted order, we collect the small divisors (≤ √n) in one list and the large divisors (> √n) in another, then combine them.

Step-by-Step Explanation

Let's trace through with n = 36 (√36 = 6):

Step 1: Initialize two lists: small_divisors = [], large_divisors = []. We will iterate i from 1 to √36 = 6.

Step 2: i = 1. Check 36 % 1 = 0 → divisor! Pair: (1, 36). Add 1 to small_divisors, add 36 to large_divisors.

  • small = [1], large = [36]

Step 3: i = 2. Check 36 % 2 = 0 → divisor! Pair: (2, 18). Add 2 to small, 18 to large.

  • small = [1, 2], large = [36, 18]

Step 4: i = 3. Check 36 % 3 = 0 → divisor! Pair: (3, 12). Add 3 to small, 12 to large.

  • small = [1, 2, 3], large = [36, 18, 12]

Step 5: i = 4. Check 36 % 4 = 0 → divisor! Pair: (4, 9). Add 4 to small, 9 to large.

  • small = [1, 2, 3, 4], large = [36, 18, 12, 9]

Step 6: i = 5. Check 36 % 5 = 1 → NOT a divisor. Skip.

Step 7: i = 6. Check 36 % 6 = 0 → divisor! But 36/6 = 6 = i → perfect square case! Both divisors in the pair are the same. Add 6 to small ONLY (do not add duplicate).

  • small = [1, 2, 3, 4, 6], large = [36, 18, 12, 9]

Step 8: Loop finished (i > √36). Reverse large_divisors to get ascending order: [9, 12, 18, 36]. Combine: small + reversed_large = [1, 2, 3, 4, 6, 9, 12, 18, 36].

Result: [1, 2, 3, 4, 6, 9, 12, 18, 36] — found all 9 divisors with only 6 iterations instead of 36!

Optimal — Finding Divisor Pairs up to √n — Watch how iterating only up to √n discovers ALL divisors by exploiting the pairing property: if i divides n, then n/i is also a divisor.

Algorithm

  1. Initialize two lists: small_divisors (for divisors ≤ √n) and large_divisors (for divisors > √n)
  2. Iterate i from 1 to √n (inclusive):
    • If n % i == 0:
      • Add i to small_divisors
      • If i ≠ n/i (not a perfect square case), also add n/i to large_divisors
  3. Reverse large_divisors to get descending-to-ascending order
  4. Concatenate small_divisors + reversed large_divisors
  5. Return the combined sorted list

Code

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

vector<int> allDivisors(int n) {
    vector<int> small_div, large_div;
    
    // Only iterate up to sqrt(n)
    for (int i = 1; i <= (int)sqrt((double)n); i++) {
        if (n % i == 0) {
            small_div.push_back(i);      // i is a divisor <= sqrt(n)
            if (i != n / i) {
                large_div.push_back(n / i); // n/i is paired divisor > sqrt(n)
            }
        }
    }
    
    // large_div is in descending order, reverse it
    reverse(large_div.begin(), large_div.end());
    
    // Combine: small_div is ascending, reversed large_div is ascending
    for (int d : large_div) {
        small_div.push_back(d);
    }
    
    return small_div;
}

int main() {
    int n = 36;
    vector<int> result = allDivisors(n);
    
    for (int d : result) {
        cout << d << " ";
    }
    // Output: 1 2 3 4 6 9 12 18 36
    
    return 0;
}
import math

def all_divisors(n: int) -> list:
    small_div = []
    large_div = []
    
    # Only iterate up to sqrt(n)
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            small_div.append(i)        # i is a divisor <= sqrt(n)
            if i != n // i:
                large_div.append(n // i)  # n//i is paired divisor > sqrt(n)
    
    # large_div is in descending order; reverse and combine
    result = small_div + large_div[::-1]
    return result

n = 36
print(*all_divisors(n))  # Output: 1 2 3 4 6 9 12 18 36
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class AllDivisorsOptimal {
    public static List<Integer> allDivisors(int n) {
        List<Integer> smallDiv = new ArrayList<>();
        List<Integer> largeDiv = new ArrayList<>();
        
        // Only iterate up to sqrt(n)
        for (int i = 1; i <= (int) Math.sqrt(n); i++) {
            if (n % i == 0) {
                smallDiv.add(i);          // i is a divisor <= sqrt(n)
                if (i != n / i) {
                    largeDiv.add(n / i);  // n/i is paired divisor > sqrt(n)
                }
            }
        }
        
        // Reverse largeDiv and combine
        Collections.reverse(largeDiv);
        smallDiv.addAll(largeDiv);
        
        return smallDiv;
    }
    
    public static void main(String[] args) {
        int n = 36;
        List<Integer> result = allDivisors(n);
        
        for (int d : result) {
            System.out.print(d + " ");
        }
        // Output: 1 2 3 4 6 9 12 18 36
    }
}

Complexity Analysis

Time Complexity: O(√n)

The loop runs from 1 to √n, performing one modulo operation per iteration. The total number of iterations is √n. For n = 10^9, that is approximately 31,623 iterations — a massive improvement over the brute force's billion iterations. The reversal of large_divisors takes at most O(√n) time as well.

Space Complexity: O(√n)

The number of divisors of n is at most O(√n) in practice (the maximum number of divisors a number up to 10^9 can have is around 1344). We store all divisors in two lists, whose combined size equals the total number of divisors. Excluding the output, the extra space for the auxiliary large_div list is O(√n).