#165EasyMath & Number Theory· Sieve of Eratosthenes

Prime Key Pool

A toy cipher picks its secret multiplier from the prime numbers strictly smaller than a limit `n`. Before shipping, the designers want to know how big the pool of possible multipliers is. Return the number of prime numbers less than `n`. Recall that a prime is an integer greater than 1 whose only positive divisors are 1 and itself, so 0 and 1 are not prime. Testing every number with trial division works for small limits but is far too slow when `n` is in the millions. Aim for a solution that does roughly `n log log n` work.

Input format

`n`: a non-negative integer.

Output format

An integer: how many primes are strictly less than `n`.

Examples

Input: n = 10

Output: 4

The primes below 10 are 2, 3, 5 and 7: four of them.

Input: n = 2

Output: 0

The only candidate below 2 would be 0 or 1, and neither is prime.

Input: n = 30

Output: 10

The primes below 30 are 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29.

Constraints

0 <= n <= 5 * 10^6

#math
#number-theory
#sieve
#arrays