<p>Given an integer <code>n</code>, return <em>the number of prime numbers that are strictly less than</em> <code>n</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 10
<strong>Output:</strong> 4
<strong>Explanation:</strong> There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 0
<strong>Output:</strong> 0
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 1
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= n &lt;= 5 * 10<sup>6</sup></code></li>
</ul>

static const auto _ = []() -> int {
    std::ios::sync_with_stdio(false);
    std::cin.sync_with_stdio(false);
    std::cout.sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();

constexpr std::size_t n{5'000'001};
constexpr auto sieve = []() {
    struct factors_t {
        std::array<bool, n> primes;
        std::array<int, n> least_prime;
    } factors;
    factors.primes.fill(true);
    factors.least_prime.fill(-1);

    factors.primes[0] = factors.primes[1] = false;
    for (std::size_t i = 2; i < n; ++i) {
        if (factors.primes[i] && (std::int64_t)i * i <= n) {
            if (factors.least_prime[i] == -1) {
                factors.least_prime[i] = i;
            }
            for (std::size_t j = i * i; j < n; j += i) {
                factors.primes[j] = false;
                if (factors.least_prime[j] == -1) {
                    factors.least_prime[j] = i;
                }
            }
        }
    }
    return factors;
};
static const inline auto sieve_ {sieve()};
class Solution {
public:
    int countPrimes(int n) {
        int res{0};
        for (int i = 0; i != n; ++i){
            res += sieve_.primes[i];
        }
        return res;
    }
};
31380