☕ DSA Java Articles

Topics › Basics › Know Basic Maths

Print all Divisors

Easy TUF ID 2807 A2Z

Java source ↗ Edit this article ↗

Problem

You are given a positive integer n. Return all of its positive divisors (every d with n % d == 0) in increasing order. 1 and n are always included.

Constraints: 1 ≤ n ≤ 2^31 - 1. The number of divisors k is small compared to n (an int has at most 1600 divisors), so the output is never the bottleneck; the search for them is.

Example 1

n = 36
answer = [1, 2, 3, 4, 6, 9, 12, 18, 36]

Example 2

n = 13
answer = [1, 13]    // 13 is prime

Example 3

n = 1
answer = [1]

Approach 1: Brute force, test every candidate

Intuition. A divisor of n is at most n, so test every integer from 1 to n with one modulo operation each. Because candidates are visited in increasing order, the output comes out sorted for free.

Algorithm.

  1. Create an empty list.
  2. For d from 1 to n: if n % d == 0, append d.
  3. Return the list.
static List<Integer> bruteForce(int n) {
    List<Integer> result = new ArrayList<>();
    for (int d = 1; d <= n; d++) {
        if (n % d == 0) result.add(d);
    }
    return result;
}

Complexity. Time O(n), one % per candidate; for n = 10^9 that is a billion operations. Space O(k) for the k divisors.

An easy halving is to stop at n / 2 and append n manually, since no divisor other than n exceeds n / 2. That is still O(n). The real improvement comes from noticing that divisors pair up.

Approach 2: Better, divisors come in pairs

Intuition. If d divides n, then so does n / d, and one of the two is at most sqrt(n): if both were larger than sqrt(n), their product would exceed n. So every divisor is either some d ≤ sqrt(n) or the partner n / d of such a d. Scanning only 1..sqrt(n) and emitting both members of each pair finds everything.

Two details. When n is a perfect square, d = sqrt(n) is its own partner, so add it once. And the pairs come out in a mixed order (1, 36, 2, 18, 3, 12, ...), so sort at the end.

Algorithm.

  1. For d = 1 while d * d ≤ n:
    • if n % d == 0, add d; if d != n / d, also add n / d.
  2. Sort the list and return it.
static List<Integer> better(int n) {
    List<Integer> result = new ArrayList<>();
    for (int d = 1; (long) d * d <= n; d++) {
        if (n % d == 0) {
            result.add(d);
            if (d != n / d) result.add(n / d);
        }
    }
    Collections.sort(result);
    return result;
}

Complexity. Time O(sqrt(n) + k log k): about 46341 iterations for the largest int, plus a sort of the k divisors. Space O(k).

The loop condition is written as (long) d * d <= n rather than d <= Math.sqrt(n) for two reasons: it avoids floating-point rounding at perfect squares, and the cast prevents d * d from overflowing int when n is close to 2^31 - 1 (there d reaches 46341 and 46341^2 = 2147488281 would wrap to a negative number, making the loop run far too long or forever).

Approach 3: Optimal, two lists instead of a sort

Intuition. The small divisors d are discovered in increasing order, and their partners n / d are discovered in decreasing order. Keep them in two separate lists. The answer is the first list followed by the second list reversed; no comparison sort is needed, and we still visit each candidate once.

Algorithm.

  1. small = [], large = [].
  2. For d = 1 while d * d ≤ n: if n % d == 0, append d to small; if d != n / d, append n / d to large.
  3. Append the elements of large to small from last to first.
  4. Return small.
static List<Integer> optimal(int n) {
    List<Integer> small = new ArrayList<>();
    List<Integer> large = new ArrayList<>();
    for (int d = 1; (long) d * d <= n; d++) {
        if (n % d == 0) {
            small.add(d);
            if (d != n / d) large.add(n / d);
        }
    }
    for (int i = large.size() - 1; i >= 0; i--) small.add(large.get(i));
    return small;
}

Dry run on n = 36 (sqrt(36) = 6):

d 36 % d == 0? small large
1 yes [1] [36]
2 yes [1, 2] [36, 18]
3 yes [1, 2, 3] [36, 18, 12]
4 yes [1, 2, 3, 4] [36, 18, 12, 9]
5 no    
6 yes, and 6 == 36 / 6 [1, 2, 3, 4, 6] unchanged

Appending large in reverse gives [1, 2, 3, 4, 6, 9, 12, 18, 36].

Complexity. Time O(sqrt(n)), with no sort. Space O(k) for the two lists (the output itself).

In practice the sort in Approach 2 is negligible because k is tiny, so both are fine in an interview; Approach 3 is simply the cleaner argument. If you need only the count or the sum of divisors, drop the lists and accumulate a counter or a long sum in the same loop.

Edge cases and pitfalls