function countPrimes(n): if n <= 2: return 0
isPrime = array of size n, all true isPrime[0] = isPrime[1] = false
for p from 2 to sqrt(n): if isPrime[p]: for multiple from p*p to n-1 step p: isPrime[multiple] = false
count = 0 for i from 0 to n-1: if isPrime[i]: count += 1 return count