Given an integer n, return the number of prime numbers strictly less than n. n can be as large as 5,000,000.
Before you code
Use the limit to choose the algorithm, as the lesson describes. Testing each number for divisors up to its square root costs about n√n steps: around 10¹⁰ for n = 5,000,000, which is far too slow. You need something close to linear.
Hints
- The sieve of Eratosthenes starts with every number marked as possibly prime. For each prime p, it crosses out p², p² + p, p² + 2p and so on.
- Start crossing out at p², because smaller multiples of p were already crossed out by smaller primes. Stop once p² ≥ n.
- The total work is about n log log n, which grows so slowly that it behaves almost like O(n).
- Use a byte array or a bit array for the marks; a list of booleans in Python works but is several times larger.
Production & complexity notes
When solving Count primes on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Growth rates and Big-O to reinforce the underlying pattern.
What it practices
Turning an input limit into a growth rate you can afford, from Growth rates and Big-O.