Count Primes

Editorial

Count Primes is a classic number-theory interview problem best solved with the Sieve of Eratosthenes: count how many primes are ≤ n.

Approach

Mark everything prime, then for each prime p from 2 upward, cross out its multiples starting at p². Starting at p² rather than 2p avoids redundant work, since smaller multiples were already crossed out by smaller primes.

sieve = [True]*(n+1)
sieve[0] = sieve[1] = False
for p in range(2, int(n**0.5)+1):
    if sieve[p]:
        for m in range(p*p, n+1, p):
            sieve[m] = False
return sum(sieve)

Complexity

Time: O(n log log n). Space: O(n).