Primes & Factorisation

Sieve of Eratosthenes

To list every prime below n, do not test each number. Start with all numbers marked prime, walk from 2, and for each prime cross off its multiples starting at p*p. Everything left standing is prime. O(n log log n), which is close enough to linear that it is effectively free.

O(n log log n)

O(n)

say this out loud

I need all primes below n, so I sieve rather than test each number. Crossing off from p squared makes it O(n log log n), effectively linear.

How It Works

The sieve inverts the obvious approach. Instead of asking of each number whether it is prime, it assumes everything is prime and then crosses off what cannot be. Walk upward from 2; when you reach a number still standing, it is prime, because nothing below it divided it. Then strike out its multiples.

The two optimisations are what people get wrong. Start crossing off at p*p rather than 2p: any multiple of p below p*p has a smaller prime factor and was already removed when that factor was processed. And stop the outer loop at sqrt(n), because a composite below n must have a factor at or below its own square root, so it has already been struck. The cost is O(n log log n), which is close enough to linear that a sieve to ten million runs in well under a second. Compare that to testing each number by trial division, which is O(n sqrt n) and is the difference between instant and unusable.

Step-by-Step Visualization

Find every prime up to 10. All nine candidates start unmarked

primesnone yet

1/8

Code

Java

static boolean[] sieve(int n) {
  boolean[] isPrime = new boolean[n + 1];
  Arrays.fill(isPrime, 2, n + 1, true);

  for (int p = 2; (long) p * p <= n; p++) {
    if (!isPrime[p]) continue;           // already crossed off
    for (int m = p * p; m <= n; m += p)  // start at p*p
      isPrime[m] = false;
  }
  return isPrime;
}

Tips & Gotchas

1Start crossing off at p*p, not 2p: everything below p*p already has a smaller factor

2Stop the outer loop at sqrt(n), since any composite left has a factor below its root

3Use boolean[] not Set: the array is the whole point and it is cache friendly

Practice Problems

1Count Primes
2Ugly Number II
3Perfect Squares
4Closest Prime Numbers in Range

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 start crossing off at p*p instead of 2p?

Every multiple of p below p*p can be written as p times something smaller than p, so it carries a prime factor below p. That factor was processed on an earlier pass and already struck the number out. Starting at p*p skips redundant work and is the difference between the sieve and a slower rewrite of it.

When is the sieve the wrong tool?

When you need primality for one large number rather than all primes below a bound. A sieve to 10^12 needs 10^12 slots. For a single value use trial division to sqrt(n), or Miller-Rabin if the number is genuinely huge. Sieve when the question is about a range, test when it is about one number.

How much memory does it actually use?

A boolean[] in Java is one byte per entry, so a sieve to 10^7 is about 10 MB, which is fine. Past that, switch to a bitset for an eightfold saving, or a segmented sieve that processes fixed-size windows so memory stays constant while the range grows.