A fence has posts numbered 0, 1, ..., n - 1. Posts with a prime number get a lantern. Return how many lanterns are needed, i.e. the number of primes strictly less than n.
Examples
Input: n = 10
Output: 4
Explanation: 2, 3, 5 and 7.
Input: n = 2
Output: 0
Constraints
0 <= n <= 10**6- Target complexity: O(n log log n) time, O(n) space.
Goals
- Cross out multiples instead of testing each number separately
- Start crossing out at p * p and stop at sqrt(n)
- Use a bytearray and slice assignment for speed