☕ DSA Java Articles

Topics › Bit Manipulation › Advanced Maths

Divisors of a Number

Easy TUF ID 370 A2Z

Java source ↗ Edit this article ↗

Problem

You are given a positive integer n. Return all of its positive divisors, that is every d with n % d == 0, in increasing order. 1 and n are always divisors. A follow-up often asked in the same breath is to return only the count of divisors, which has a neat closed form once you know the prime factorisation.

Constraints: 1 ≤ n ≤ 2^31 - 1. No 32-bit integer has more than 1600 divisors, so the output is never the bottleneck; the search is.

Example 1

n = 36
answer = [1, 2, 3, 4, 6, 9, 12, 18, 36]      // 9 divisors; 36 is a perfect square so 6 appears once

Example 2

n = 7
answer = [1, 7]                               // a prime has exactly two divisors

Example 3

n = 1
answer = [1]

Approach 1: Brute force

Intuition. Check every number from 1 to n. The output is naturally sorted because candidates are tested in increasing order. The cost is one modulo per candidate, and there are n candidates even though only a handful can succeed.

Algorithm.

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

Complexity. Time O(n): one modulo per candidate. Space O(k) for the k divisors.

For n around 2 × 10^9 that is two billion modulo operations, several seconds of work for an answer with at most 1600 entries.

Approach 2: Better, pair each divisor with its partner

Intuition. Divisors come in pairs. If d divides n, then n / d is an integer and also divides n. In every such pair (d, n / d) one member is at most sqrt(n) and the other is at least sqrt(n), because if both were larger than sqrt(n) their product would exceed n, and if both were smaller it would fall short. So it is enough to test d from 1 up to sqrt(n); each hit yields d and its partner. The one subtlety is a perfect square, where d == n / d and the partner must not be recorded twice. The hits arrive out of order (small d, big partner, slightly bigger d, slightly smaller partner, …), so sort at the end.

Algorithm.

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

Complexity. Time O(sqrt(n) + k log k): about sqrt(n) modulo operations plus sorting k divisors. For n = 2^31 - 1 that is roughly 46000 iterations instead of two billion. Space O(k).

Approach 3: Optimal, merge the two halves without sorting

Intuition. Look at the order in which Approach 2 produces values. The small members d arrive in increasing order (because d increases), and their partners n / d arrive in decreasing order (because dividing n by a larger d gives a smaller result). Every small member is at most sqrt(n) and every partner is at least sqrt(n). So keep the two groups in separate lists: small is already sorted ascending, large is sorted descending, and every element of large exceeds every element of small. The final answer is small followed by large read backwards. No sort, no comparison function, and the output falls out in O(k).

Algorithm.

  1. For d from 1 while d × d ≤ n:
  2. If n % d == 0, append d to small, and append n / d to large if it differs from d.
  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 (long d = 1; d * d <= n; d++) {
        if (n % d == 0) {
            small.add((int) d);
            if (d != n / d) large.add((int) (n / d));
        }
    }
    for (int i = large.size() - 1; i >= 0; i--) small.add(large.get(i));
    return small;
}

Dry run on n = 36:

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

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

Complexity. Time O(sqrt(n)): the scan dominates and the merge is linear in the output. Space O(k) for the two lists, which together hold exactly the answer.

Variant: counting divisors without listing them

If the question is only “how many divisors”, there is a formula. Write n = p1^e1 × p2^e2 × ... × pk^ek. A divisor picks an exponent for each prime independently, from 0 to ei, so the number of divisors is (e1 + 1)(e2 + 1)...(ek + 1). For 36 = 2^2 × 3^2 that is 3 × 3 = 9, matching the list above. The factorisation is found by trial division up to sqrt(n), stripping each prime as it is found so that composites never divide the shrinking n.

static int countDivisors(int n) {
    int count = 1;
    for (long p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            int exponent = 0;
            while (n % p == 0) {
                n /= p;
                exponent++;
            }
            count *= exponent + 1;
        }
    }
    if (n > 1) count *= 2;        // one leftover prime with exponent 1
    return count;
}

This is also O(sqrt(n)), but it needs no list, and the same loop structure gives you the sum of divisors (∏ (p^(e+1) - 1) / (p - 1)) or any other multiplicative function.

Edge cases and pitfalls