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).
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
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.