#204 Count Primes
the problem
In plain words
Given an integer n, count the prime numbers that are smaller than n (n itself does not count, even when it is prime).
in n = 10
out 4
The primes below 10 are 2, 3, 5 and 7.
in n = 0
out 0
in n = 1
out 0
- 0 ≤ n ≤ 5·10⁶
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternGCD & prime sieve
where this runsFor large primes (95 bits and up), the JDK's own BigInteger.probablePrime sieves away candidates with small factors (java.math.BitSieve) before running its expensive primality test — the same crossing-off idea.
Don't test numbers one by one — cross them off in bulk. Each prime p rules out all its multiples, starting at p² (smaller multiples already fell to smaller primes), and you can stop once p² ≥ n. Whatever survives is prime.
solutions
From brute force to optimal
For each k from 2 to n − 1, try divisors up to √k; count the ones with no divisor.
- For k in 2..n−1: is k prime?
- Try d = 2, 3, … while d * d ≤ k; any k % d == 0 means composite.
- Count the primes.
Up to √k divisions for each of n numbers (primes need all of them): about 6.5·10⁸ divisions for n = 5·10⁶.
A counter and a loop variable.
class Solution { public int countPrimes(int n) { int count = 0; for (int k = 2; k < n; k++) // every candidate below n if (isPrime(k)) count++; return count; } private boolean isPrime(int k) { for (int d = 2; (long) d * d <= k; d++) // divisors pair up as d × (k / d): one is ≤ √k if (k % d == 0) return false; return true; }}Mark composites in a boolean[n]: each surviving p crosses p², p² + p, …; count the unmarked numbers from 2.
- composite = new boolean[n] (Java fills it with false).
- For p = 2 while p * p < n: if !composite[p], mark m = p², p² + p, … below n.
- Count k in 2..n−1 with !composite[k].
Prime p crosses about n / p cells; summed over primes that is O(n log log n) — 11,192,868 crossings for n = 5·10⁶.
One boolean per number: about 5 MB for n = 5·10⁶.
class Solution { public int countPrimes(int n) { boolean[] composite = new boolean[n]; // all false: everything starts as "maybe prime" for (int p = 2; (long) p * p < n; p++) { // a composite below n has a prime factor p with p * p < n if (composite[p]) continue; // its multiples were crossed by a smaller prime for (int m = p * p; m < n; m += p) // k * p with k < p was crossed already composite[m] = true; } int count = 0; for (int k = 2; k < n; k++) if (!composite[k]) count++; // the survivors are the primes below n return count; }}Dry run
in the room
How to say it in the interview
talk track
- Clarify the boundary first: "strictly less than n", so countPrimes(5) is 2, not 3.
- Give trial division in one line and its cost, then say: "for all numbers up to n, a sieve crosses off multiples in bulk."
- Explain the two optimisations out loud: start at p² (smaller multiples are already crossed) and stop when p² ≥ n.
traps
- Counting n itself: the loops must use
< n, not<= n. - Starting the crossing at 2p instead of p² — still correct, just slower; starting at p would cross p itself out.
p * pinintoverflows once p > 46,340 if n were bigger —(long) p * p < nis the safe habit.
what they ask next
Follow-ups
Memory is tight — what then?
Sieve only odd numbers (half the memory), use a BitSet (one bit per number), or a segmented sieve that processes √n-sized blocks.
Can a sieve be O(n)?
Yes: the linear sieve crosses every composite exactly once, through its smallest prime factor. It also gives smallest prime factors for fast factorisation.
before you submit
Edge cases to test
- n = 0, 1 or 2 → 0 (count primes strictly below n, so 2 itself is not counted for n = 2)
- n prime, e.g. n = 5 → 2: n itself is never counted
- Squares of primes: n = 26 needs 25 = 5 × 5 crossed, n = 50 needs 49 = 7 × 7
- Large n (5·10⁶ on LeetCode): a sieve is fine, trial division of every number is not
practise next
Similar problems
- #338Counting BitsEasyin Bits
- #69Sqrt(x)Easyin Big-O
- #172Factorial Trailing ZeroesMediumin Math & Numbers