Count Primes

Difficulty: Medium · Topic: Math for algorithms

Return the number of prime numbers strictly less than n. Trial-dividing each number is slow; the Sieve of Eratosthenes marks composites in O(n log log n).

Examples

count_primes(10)
→ 4

2, 3, 5, 7.

count_primes(2)
→ 0

Target complexity: time O(n log log n), space O(n)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.