Primes & Factorisation

Prime Factorisation

Divide out each factor from 2 upward, dividing repeatedly while it divides evenly. Stop the loop at sqrt(n): whatever remains above 1 at the end is itself a prime factor. O(sqrt n) per number, and the divide-while loop is what makes it correct for repeated factors like 8 = 2^3.

O(sqrt n)

O(log n)

say this out loud

I divide out each factor from two upward, repeating while it divides, and stop at the square root. Whatever is left above one is itself prime.

How It Works

Trial division works because of one fact: if n is composite, it has a factor at or below sqrt(n). So loop a candidate divisor f from 2 up to sqrt(n), and whenever f divides n, divide it out and keep dividing while it still divides. That inner while loop is what handles repeated factors correctly, so 8 yields 2, 2, 2 rather than a single 2.

The detail worth noticing is that n shrinks as you divide, so the loop bound falls with it and the real work is far less than sqrt of the original. Once the loop ends, anything left above 1 is itself prime and must be added: factorising 14 leaves 7 stranded after f passes 3, and forgetting that final check is the standard bug. You never need to test whether f is prime, because by the time you reach a composite f, all of its prime factors have already been divided out of n.

Step-by-Step Visualization

Factorise 60 by trial division, starting from 2

n60

factorsnone

1/8

Code

Java

static List<Integer> factorize(int n) {
  List<Integer> factors = new ArrayList<>();

  for (int f = 2; (long) f * f <= n; f++) {
    while (n % f == 0) {   // repeated factors
      factors.add(f);
      n /= f;
    }
  }
  if (n > 1) factors.add(n);  // leftover is prime
  return factors;
}

Tips & Gotchas

1Divide while it divides, not once: 8 has factor 2 three times

2Loop to sqrt(n) only, then whatever is left above 1 is itself prime

3n shrinks as you divide, so the real loop is far shorter than sqrt of the original

Practice Problems

1Factorial Trailing Zeroes
2Largest Prime Factor
3Distinct Prime Factors of Product of Array
4Four Divisors

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 is it safe to divide by composite candidates like 4 or 6?

It never happens. By the time f reaches 4, every factor of 2 has already been divided out, so n % 4 cannot be zero. Any composite candidate has its prime factors removed before you get there, which is why the loop needs no primality check and stays three lines long.

Why does the leftover above 1 have to be prime?

The loop removed every factor at or below sqrt of the current n. If something remains, it has no factor below its own square root, which is the definition of prime. This is the case for any number with one large prime factor, like 2 x 499, where 499 survives to the end.

How do I factorise many numbers quickly?

Precompute a smallest-prime-factor table with a sieve. Then factorising any number is repeatedly dividing by spf[n], which is O(log n) per query instead of O(sqrt n). This is the standard setup when a problem factorises every element of a large array.