It seems surprising that the best known algorithm for computing π(n) (the number of primes ≤ n) takes time Õ(n^(2/3). I would have naively expected that something Õ(n^(1/2)) is possible, sieving only over numbers k < n^(1/2), but apparently the region [n^(1/2), n] is too messy.