Count Primes
Count how many prime numbers are strictly less than a given integer n.
Open on LeetCode ↗Intuition
There are two wrong turns here and the second one catches people who already avoided the first. The obvious mistake is testing each number for primality by trial division — that is O(n sqrt n) and dies well before n = 5,000,000. So you reach for the Sieve of Eratosthenes: assume everything is prime, then let each prime cross out its own multiples. Good. But now the subtle one: you write the inner loop as for j in range(i2, n, i), and you have just quietly doubled the work. Think about what happens when i = 7 — the sieve crosses out 14, 21, 28, 35, 42 — every one of those was already struck by 2, 3, 2, 5, 2 respectively. Any multiple of i below ii has a factor smaller than i, and that smaller factor already had its turn. So start at ii. The same reasoning caps the outer loop: once ii >= n there is nothing left to cross, so stop at sqrt(n). That is the invariant — when the outer loop reaches i, every composite with a prime factor below i has already been struck, so anything still standing at i is prime.
Approach
Invert the question: mark composites, do not test primes
Primality testing asks 'does anything divide this number?', which forces a search for every candidate. The sieve asks the opposite question — 'what does this number divide?' — and each prime answers it by walking its own multiples in a single arithmetic progression. Allocate a boolean array of size n, set everything True, and immediately strike 0 and 1, which are prime by neither definition nor convention. Every entry still True at the end is a prime.
Start the inner marking at i*i, not i*2
When you arrive at a prime i, every multiple ik with k < i contains the smaller factor k, and if k is composite it contains a smaller prime still. Either way, a prime below i already visited that number and crossed it out. The first multiple of i that nothing smaller could have reached is ii, so that is where marking begins. This is not a micro-optimisation — it is what turns the total work into the sum of n/p over primes p, which is O(n log log n).
Stop the outer loop at sqrt(n), then count the survivors
The outer loop only needs to run while ii < n. Past that point, ii is out of range and there is nothing for i to mark, so continuing changes nothing. Numbers between sqrt(n) and n are still correctly classified: any composite in that band has a factor below sqrt(n) and was struck by it. Finish by summing the array — the count of True entries from index 2 upward is the answer.
Solution & live demo
Edge cases
There are no primes below 1, so the array is empty or holds only index 0; the count is 0.
The problem counts primes strictly below n, so 2 itself does not qualify — the answer is 0.
The outer loop skips any i already marked composite; all of its multiples share the smaller prime factor that struck it and are already gone.
The sieve holds one boolean per number, which is O(n) memory but linear-ish time — the trial-division alternative would not finish at all.