Write count_primes(n: int) -> int that returns how many primes are strictly less than n.
Testing each number by trial division is far too slow for n in the millions; aim for about O(n log log n).
count_primes(10) # 4 (2, 3, 5, 7)
count_primes(2) # 0
count_primes(0) # 0
count_primes(3) # 1
Constraints: 0 ≤ n ≤ 5·10^6.
Show hint
Rather than testing numbers one at a time, work from the primes outward: each prime p rules out all of its multiples (starting from p·p is enough). In Python, a bytearray with slice assignment (marks[p*p::p] = bytes(len(range(p*p, n, p)))) clears a whole row at C speed.