Math — Count Primes (Sieve of Eratosthenes)

solve(n) — return how many prime numbers are strictly less than n (0 <= n <= 5 000 000).
Testing every number for primality by trial division is O(n√n); the **sieve of
Eratosthenes** does it in O(n log log n).

Keep a boolean per number, all true at first. For each p still marked prime, cross out its
multiples. Two optimisations make it fast: start crossing out at p * p (smaller multiples
were already removed by smaller primes), and stop the outer loop once p * p >= n.

Examples

solve(10)    → 4        // 2, 3, 5, 7
solve(2)     → 0
solve(100)   → 25