Print All Divisors of a Number
Given an integer n, return all of its divisors. Order does not matter.
Intuition
Divisors never come alone. If i divides n, then n / i is also a whole number and is therefore a divisor too — they arrive as a pair whose product is exactly n. Every such pair has one member at or below sqrt(n) and one at or above it, so a loop that only reaches sqrt(n) still meets every pair, once each. One divisibility test hands you two divisors, and the scan drops from O(n) to O(sqrt n).
Divisors come in pairs (i, n/i) straddling √n, so iterating to the square root finds both halves at once. The n // i != i guard handles perfect squares, where the pair collapses to a single value that must not be emitted twice.
Approach
The linear scan, and why it is wasteful
Loop i from 1 to n and collect every i where n % i == 0. For n = 36 that finds 1, 2, 3, 4, 6, 9, 12, 18, 36. Correct, O(n), and it does far more work than necessary — over half its iterations are spent past the point where anything new can be discovered cheaply.
Notice that divisors pair up
For n = 36: 1 x 36, 2 x 18, 3 x 12, 4 x 9, 6 x 6. Each divisor below 6 is matched with one above it. So the moment we discover that 2 divides 36, we get 18 for free — no test required. The pairs meet at 6 = sqrt(36), which is why the small member of every pair is at most sqrt(n).
Loop to sqrt(n) and record both members
Run i from 1 while i * i <= n. Whenever n % i == 0, add i and add n / i. For 36 this tests only 1 through 6 and produces all nine divisors. The output is unsorted — 1, 36, 2, 18, 3, 12, 4, 9, 6 — so sort at the end if the problem demands ascending order, which adds an O(sqrt n log n) term.
Guard the perfect square
When n is a perfect square, the middle pair is i x i — for 36 that is 6 x 6. Adding both members would list 6 twice. Only add n / i when it differs from i. This is the single edge case that separates a working solution from an almost-working one.
Solution & live demo
Common pitfalls
Looping all the way to n
for i in range(1, n + 1):
if n % i == 0: out.append(i)while i * i <= n:
That's O(n) when O(√n) suffices — for n near 10^9 the difference is minutes versus milliseconds. Every divisor above √n is n divided by one below it, so half the loop is redundant.
Double-counting the square root
out.append(i) out.append(n // i)
out.append(i)
if n // i != i:
out.append(n // i)For a perfect square, i and n // i are the same number at the midpoint. Appending both lists it twice, which breaks a divisor count and any deduplicated output.
Using i <= sqrt(n) with floating point
while i <= math.sqrt(n):
while i * i <= n:
sqrt on large integers can round just below the true root, dropping the largest divisor pair. Integer multiplication is exact and just as fast.
Edge cases
At i = 6, n / i is also 6. The if n // i != i guard adds it once. Without the guard the output has a duplicate.
The loop runs once at i = 1; n / i is also 1, so the guard suppresses the duplicate and the answer is [1].
Only i = 1 divides it within the sqrt bound, yielding 1 and n — exactly the two divisors a prime has.