Introduction

If you need all divisors of one positive integer, the best practical method is to scan only up to the square root and collect divisor pairs. That gives the same result as checking every number from 1 to n, but it cuts the number of divisibility tests from linear time down to square-root time.

Use Divisor Pairs Around the Square Root

Divisors naturally come in pairs. If d divides n, then n // d also divides n. That means once you have checked every candidate up to sqrt(n), you have found every divisor pair already.

For 36, the pairs are 1 and 36, 2 and 18, 3 and 12, 4 and 9, and 6 and 6. After the square root, every new divisor would just mirror one you already found.

Baseline and Efficient Implementation

The naive method is easy to understand, but it does too much work.

1def divisors_naive(n: int) -> list[int]:
2    result = []
3    for candidate in range(1, n + 1):
4        if n % candidate == 0:
5            result.append(candidate)
6    return result

A better implementation uses the divisor-pair idea directly.

1import math
2
3
4def divisors(n: int) -> list[int]:
5    if n <= 0:
6        raise ValueError("n must be positive")
7
8    small = []
9    large = []
10
11    for candidate in range(1, math.isqrt(n) + 1):
12        if n % candidate == 0:
13            small.append(candidate)
14            partner = n // candidate
15            if partner != candidate:
16                large.append(partner)
17
18    return small + large[::-1]
19
20
21print(divisors(28))
22print(divisors(36))

This returns sorted divisors and avoids duplicating the square root for perfect squares.

Why This Is Faster

The naive solution performs n modulus operations. The square-root method performs about sqrt(n) checks. For a number around one million, that means roughly one thousand checks instead of one million.

The memory cost is modest because you store only the divisors you actually find. For typical values, the divisor count is tiny compared with the size of the number itself.

Counting Divisors Instead of Listing Them

Sometimes you need only the count, not the list. In that case, prime factorization is often the right tool. If

n = p1^a1 * p2^a2 * ...

then the number of positive divisors is

(a1 + 1) * (a2 + 1) * ...

Here is a simple Python implementation.

1def prime_factors(n: int) -> dict[int, int]:
2    factors = {}
3    d = 2
4    while d * d <= n:
5        while n % d == 0:
6            factors[d] = factors.get(d, 0) + 1
7            n //= d
8        d += 1 if d == 2 else 2
9    if n > 1:
10        factors[n] = factors.get(n, 0) + 1
11    return factors
12
13
14def divisor_count(n: int) -> int:
15    total = 1
16    for exponent in prime_factors(n).values():
17        total *= exponent + 1
18    return total
19
20
21print(divisor_count(360))

That is useful when a problem asks how many divisors exist rather than what they are.

Handle Edge Cases Explicitly

You should decide what your function means for special inputs. 1 has one positive divisor, which is 1. 0 is usually rejected in programming utilities because every nonzero integer divides 0, so the divisor set is not finite. Negative numbers are domain-specific. Some programs return divisors of the absolute value, while others reject negatives entirely.

Clear input rules matter more than clever code here.

Common Pitfalls

• Checking every number up to n when scanning to sqrt(n) is enough.
• Forgetting to append the paired divisor n // d after finding d.
• Duplicating the square-root divisor for perfect squares.
• Returning divisors in an unexpected order because the large partners were not reversed.
• Failing to define behavior for 0, 1, or negative input values.

Summary

• The best general method for one number is scanning up to the square root.
• Divisors come in pairs, so each successful check yields one or two results.
• This reduces time from O(n) to O(sqrt(n)).
• Prime factorization is useful when you need divisor counts.
• Explicit edge-case handling makes the function predictable and reusable.