Primes & Factorisation

Divisors & Counting

Divisors come in pairs that multiply to n, so loop i to sqrt(n) and take both i and n/i. Careful with perfect squares, where i equals n/i and must be counted once. Divisor counts also fall straight out of the prime factorisation exponents.

O(sqrt n)

say this out loud

Divisors come in pairs multiplying to n, so one loop to the square root finds both. I only have to remember not to count the root twice.

How It Works

Divisors come in pairs. If i divides n then so does n/i, and one of the pair is always at or below sqrt(n). So a single loop from 1 to sqrt(n) discovers every divisor: collect i on the way up and n/i as its partner. That turns an O(n) scan into O(sqrt n), which for n around a billion is about 31,600 iterations instead of a billion.

The one trap is the perfect square. When n is 36 and i reaches 6, the pair is (6, 6) and adding both double-counts it, so guard with a check that i does not equal n/i. If you need the count rather than the list, the prime factorisation gives it directly: for n = p1^a * p2^b, the divisor count is (a+1)(b+1), because each prime can appear anywhere from zero to its full exponent independently.

Step-by-Step Visualization

Find every divisor of 12

found0

1/7

Code

Java

static List<Integer> divisors(int n) {
  List<Integer> small = new ArrayList<>(), large = new ArrayList<>();

  for (int i = 1; (long) i * i <= n; i++) {
    if (n % i != 0) continue;
    small.add(i);
    if (i != n / i) large.add(n / i);  // skip the root twice
  }
  Collections.reverse(large);
  small.addAll(large);
  return small;
}

Tips & Gotchas

1Divisors pair up: if i divides n, so does n/i. One loop to sqrt finds both

2Perfect squares double-count the root, so add it once when i == n/i

3For divisor counts, multiply (exponent + 1) across the prime factorisation

Practice Problems

1Four Divisors
2Count Number of Nice Subarrays
3Number of Divisors
4Bulb Switcher

About the Primes & Factorisation Pattern

Everything about primes comes down to one observation: a composite number always has a factor at or below its square root. That single fact turns primality testing into a sqrt loop and turns 'all primes below n' into a sieve that marks multiples instead of testing candidates.

Key insight

Almost every math problem is asking you to avoid the obvious loop. Trial division to n becomes a sieve, repeated multiplication becomes binary exponentiation, and division under a modulus becomes multiplication by an inverse. If your solution loops to n or to the exponent, there is nearly always a log or sqrt version.

Common Math & Number Theory Interview Problems

Count Primes
Pow(x, n)
Greatest Common Divisor of Strings
Excel Sheet Column Title
Ugly Number II
Factorial Trailing Zeroes

Frequently Asked Questions

Why does Bulb Switcher come down to perfect squares?

A bulb is toggled once per divisor, so it ends up on only when its divisor count is odd. Divisors pair up, which makes the count even, except when a number is a perfect square and its root pairs with itself. So the answer is just the count of perfect squares below n, which is floor(sqrt(n)).

Should I collect divisors in sorted order?

The loop naturally produces small divisors ascending and large ones descending. Push the small ones to one list and the large ones to another, then reverse the second and concatenate. That gives sorted order in O(sqrt n) without ever calling a sort.