Count the Primes — Solution & Editorial

Back to the Problem

Sieve of Eratosthenes: cross out multiples of each prime starting at its square, then count the survivors.

Complexity: O(N log log N)