Algorithm to find all the exact divisors of a given integer

divisor algorithm

integer divisors

number theory

computational mathematics

exact divisor calculation

Algorithm to find all the exact divisors of a given integer

Master System Design with Codemia

Enhance your system design skills with over 120 practice problems, detailed solutions, and hands-on exercises.

Start Practicing Learn More

Introduction

Finding all exact divisors of an integer n means identifying every integer that divides n with zero remainder. The naive approach checks every number from 1 to n, but a much faster method only iterates up to the square root of n, collecting divisor pairs. This reduces the time complexity from O(n) to O(sqrt(n)). Divisor algorithms are foundational in number theory and appear in problems involving GCD, LCM, prime factorization, and cryptography.

The Square Root Algorithm

For any divisor i of n, the complementary divisor n / i is also a divisor. By iterating only up to sqrt(n), you find both divisors in each step:

python

1import math
2
3def get_divisors(n):
4    if n <= 0:
5        raise ValueError("n must be a positive integer")
6
7    divisors = []
8    for i in range(1, int(math.isqrt(n)) + 1):
9        if n % i == 0:
10            divisors.append(i)
11            if i != n // i:  # Avoid duplicate for perfect squares
12                divisors.append(n // i)
13    return sorted(divisors)
14
15print(get_divisors(36))
16# [1, 2, 3, 4, 6, 9, 12, 18, 36]
17
18print(get_divisors(28))
19# [1, 2, 4, 7, 14, 28]

For n = 36, sqrt(36) = 6. The loop checks 1 through 6:

i=1: 36 % 1 == 0, pair (1, 36)
i=2: 36 % 2 == 0, pair (2, 18)
i=3: 36 % 3 == 0, pair (3, 12)
i=4: 36 % 4 == 0, pair (4, 9)
i=5: 36 % 5 != 0, skip
i=6: 36 % 6 == 0, pair (6, 6) — same number, add only once

Implementations in Other Languages

Java

java

1public static List<Integer> getDivisors(int n) {
2    List<Integer> divisors = new ArrayList<>();
3    for (int i = 1; i * i <= n; i++) {
4        if (n % i == 0) {
5            divisors.add(i);
6            if (i != n / i) {
7                divisors.add(n / i);
8            }
9        }
10    }
11    Collections.sort(divisors);
12    return divisors;
13}
14// getDivisors(36) => [1, 2, 3, 4, 6, 9, 12, 18, 36]

C++

cpp

1#include <vector>
2#include <algorithm>
3
4std::vector<int> getDivisors(int n) {
5    std::vector<int> divisors;
6    for (int i = 1; i * i <= n; i++) {
7        if (n % i == 0) {
8            divisors.push_back(i);
9            if (i != n / i) {
10                divisors.push_back(n / i);
11            }
12        }
13    }
14    std::sort(divisors.begin(), divisors.end());
15    return divisors;
16}

JavaScript

javascript

1function getDivisors(n) {
2    const divisors = [];
3    for (let i = 1; i * i <= n; i++) {
4        if (n % i === 0) {
5            divisors.push(i);
6            if (i !== n / i) {
7                divisors.push(n / i);
8            }
9        }
10    }
11    return divisors.sort((a, b) => a - b);
12}
13
14console.log(getDivisors(36));
15// [1, 2, 3, 4, 6, 9, 12, 18, 36]

Counting Divisors

If you only need the count rather than the list:

python

1def count_divisors(n):
2    count = 0
3    for i in range(1, int(n**0.5) + 1):
4        if n % i == 0:
5            count += 2 if i != n // i else 1
6    return count
7
8print(count_divisors(36))  # 9
9print(count_divisors(28))  # 6

Divisors via Prime Factorization

For very large numbers, find the prime factorization first, then compute divisors from the exponents:

python

1from collections import Counter
2
3def prime_factors(n):
4    factors = []
5    d = 2
6    while d * d <= n:
7        while n % d == 0:
8            factors.append(d)
9            n //= d
10        d += 1
11    if n > 1:
12        factors.append(n)
13    return Counter(factors)
14
15def divisors_from_factors(n):
16    factors = prime_factors(n)
17    divs = [1]
18    for prime, exp in factors.items():
19        new_divs = []
20        power = 1
21        for e in range(exp + 1):
22            for d in divs:
23                new_divs.append(d * power)
24            power *= prime
25        divs = new_divs
26    return sorted(divs)
27
28print(divisors_from_factors(36))
29# 36 = 2^2 * 3^2
30# [1, 2, 3, 4, 6, 9, 12, 18, 36]

The number of divisors of n equals the product of (exponent + 1) for each prime factor. For 36 = 2^2 * 3^2, the divisor count is (2+1) * (2+1) = 9.

Special Cases

python

1# Prime numbers have exactly 2 divisors
2print(get_divisors(17))   # [1, 17]
3
4# Powers of 2
5print(get_divisors(64))   # [1, 2, 4, 8, 16, 32, 64]
6
7# Highly composite numbers have many divisors
8print(get_divisors(120))  # [1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120]
9print(len(get_divisors(120)))  # 16

Finding Divisors of All Numbers in a Range (Sieve)

When you need divisors for every number up to N, a sieve is more efficient than calling get_divisors N times:

python

1def sieve_divisors(limit):
2    divisors = [[] for _ in range(limit + 1)]
3    for i in range(1, limit + 1):
4        for multiple in range(i, limit + 1, i):
5            divisors[multiple].append(i)
6    return divisors
7
8all_divs = sieve_divisors(12)
9print(all_divs[12])  # [1, 2, 3, 4, 6, 12]
10print(all_divs[7])   # [1, 7]

This runs in O(N log N) time, which is faster than O(N * sqrt(N)) for computing divisors of all numbers from 1 to N.

Common Pitfalls

Iterating up to n instead of sqrt(n): Checking all numbers from 1 to n is O(n). Using the square root optimization reduces this to O(sqrt(n)), which matters for large inputs like n = 10^12.
Duplicate divisor for perfect squares: When n is a perfect square, i and n/i are the same at i = sqrt(n). Forgetting the i != n // i check adds a duplicate.
Integer overflow with large n: In languages like C++ or Java, i * i can overflow for large n. Use (long)i * i <= n or compare i <= n / i instead.
Not handling n = 1: The number 1 has exactly one divisor (itself). The algorithm handles this correctly, but some applications assume at least two divisors.
Returning unsorted results: The square root method collects small divisors and large divisors out of order. Sort the result if order matters, or use two lists (small and large) and merge them.

Summary

Iterate from 1 to sqrt(n), checking n % i == 0 to find divisor pairs (i, n/i)
Time complexity is O(sqrt(n)), which is optimal for a single number
Check i != n // i to avoid duplicate entries for perfect squares
For many numbers in a range, use a sieve approach in O(N log N)
The divisor count equals the product of (exponent + 1) for each prime factor