List All Positive Divisors of an Integer in Ascending Order, Then Beat Square-Root Time

Given a positive integer n, return every positive integer that divides n exactly, in ascending order.

As a follow-up, once you have a correct solution, the interviewer asked whether the running time can grow more slowly than $\sqrt{n}$.

Function Signature

def all_divisors(n: int) -> list[int]:

Rules

• A positive integer d is a divisor of n when n % d == 0.
• Return each divisor exactly once, sorted in strictly ascending order. The list always starts with 1 and ends with n.

Constraints

• 1 <= n <= 10^12
• n can exceed 2^31 - 1, so use 64-bit integers in languages with fixed-width integer types. Every value stays well within 2^53.

Examples

Example 1

Input:  n = 36
Output: [1, 2, 3, 4, 6, 9, 12, 18, 36]

36 is a perfect square (6 × 6 = 36), and the divisor 6 appears only once.

Example 2

Input:  n = 97
Output: [1, 97]

97 is prime, so its only divisors are 1 and 97.

Example 3

Input:  n = 1
Output: [1]

List All Divisors of an Integer in Ascending Order

Hints

1. Testing every candidate from 1 to n is far too slow when n is close to 10^12. Which candidates do you actually need to test?
2. Example 1 points out that 36 is a perfect square and 6 appears only once. Make sure your method neither drops nor duplicates such a divisor.
3. n can exceed 2^31 - 1, so check that your integer types and any loop-bound arithmetic cannot overflow.

Approach

Algorithm: divisors come in pairs (d, n / d), and in every pair the smaller member is at most sqrt(n). Compute r = floor(sqrt(n)) exactly: take the floating-point square root, then correct it with integer checks (decrease while r * r > n, increase while (r + 1) * (r + 1) <= n), so a rounding error near 10^12 cannot shift the bound. For each d from 1 to r with n % d == 0, append d to a low list and, if n / d != d, append n / d to a high list. Return low followed by high reversed.

Invariant: after processing d, low holds every divisor <= d in ascending order, and high holds their cofactors in descending order.

Correctness: any divisor e <= r is visited directly. Any divisor e > r has cofactor n / e < sqrt(n), so n / e <= r is visited, and e is added as its cofactor. Each divisor is added once, because the only case where a pair's two members coincide (d = n / d, i.e. n is a perfect square) is skipped. Every element of low is <= r, and every element of high is >= r + 1 or equals n / d > d, so low entirely precedes reversed high and the result is strictly ascending, starting with 1 and ending with n.

Edge cases: n = 1 gives r = 1 and returns [1] once; primes give [1, n]; perfect squares (36, 999983^2) list the square root once; values above 2^31 - 1 use 64-bit arithmetic (Java long, C++ long long), and r * r stays at most about 10^12, inside 2^53 for JavaScript.

Follow-up: trial-dividing to factor n and stopping once the remaining cofactor has no factor below its own square root is much faster when n has small prime factors, and the divisors can then be generated from the factorization and sorted. In the worst case (n prime, or a product of two primes near sqrt(n)) plain trial division still takes about sqrt(n) steps; going below that needs a sub-sqrt factoring method such as Pollard's rho with a Miller-Rabin primality test, which runs in about n^(1/4) expected steps. The output size is the number of divisors of n in every case.

• Time complexity: O(sqrt(n))
• Space complexity: O(d(n)), where d(n) is the number of divisors of n (the output size)