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.
The same sieve as Eratosthenes, but the bound is exclusive — count primes strictly below n. That single change shifts every comparison from <= to <, and summing the boolean array is faster than collecting the primes you don't need.
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
Common pitfalls
Using an inclusive upper bound
is_prime = [True] * (n + 1)
is_prime = [True] * n
The problem counts primes strictly less than n, so sizing the array to n + 1 includes n itself and overcounts by one whenever n is prime. Every loop bound has to match that exclusivity.
Not guarding small inputs
is_prime[0] = is_prime[1] = False
if n < 3:
return 0For n of 0, 1, or 2 the array is too short to index positions 0 and 1, so the initialisation throws. There are no primes below 3 anyway, so an early return is both safe and correct.
Trial dividing each number
for i in range(2, n):
if all(i % d for d in range(2, int(i**0.5)+1)): count += 1for j in range(i * i, n, i):
is_prime[j] = FalseTrial division is roughly O(n√n) and times out around n = 10^6. The sieve does the same job in near-linear time by working outward from each prime instead of inward from each candidate.
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.