Count Primes
Count Primes: count how many prime numbers are strictly less than a given integer n.
- 0 <= n <= 5 * 10⁶
Intuition
There are two wrong turns in count primes 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(i**2, 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 i**i has a factor smaller than i, and that smaller factor already had its turn. So start at i**i. The same reasoning caps the outer loop: once i**i >= 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 less than n, strictly below it. To count primes in range l to r instead, sieve to r and subtract the tally below l. That single change shifts every comparison from <= to <, and summing the boolean array is faster than collecting the primes you don't need.
Approach
Before reading on: price up what the direct approach costs here, then ask what pattern in the numbers removes the loop entirely. Aim for O(n log log n) time and O(n) space.
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
At a prime i, every multiple i*k with k < i contains the smaller factor k, and if k is composite it contains a smaller prime still. Either way, some prime below i already crossed that number out. The first multiple nothing smaller could reach is i*i, so marking starts there. This is not a micro-optimisation — it is what makes the total work the sum of n/p over primes, giving O(n log log n).
Stop the outer loop at sqrt(n), then count the survivors
The outer loop only needs to run while i**i < n. Past that point, i**i 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.