<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>

class Solution:
    def countPrimes(self, n: int) -> int:
        def prime_sieve(n):
            """returns a sieve of primes >= 5 and < n"""
            flag = n % 6 == 2
            sieve = bytearray((n // 3 + flag >> 3) + 1)
            for i in range(1, int(n**0.5) // 3 + 1):
                if not (sieve[i >> 3] >> (i & 7)) & 1:
                    k = (3 * i + 1) | 1
                    for j in range(k * k // 3, n // 3 + flag, 2 * k):
                        sieve[j >> 3] |= 1 << (j & 7)
                    for j in range(k * (k - 2 * (i & 1) + 4) // 3, n // 3 + flag, 2 * k):
                        sieve[j >> 3] |= 1 << (j & 7)
            return sieve


        def prime_list(n):
            """returns a list of primes <= n"""
            res = []
            if n > 1:
                res.append(2)
            if n > 2:
                res.append(3)
            if n > 4:
                sieve = prime_sieve(n + 1)
                res.extend(3 * i + 1 | 1 for i in range(1, (n + 1) // 3 + (n % 6 == 1)) if not (sieve[i >> 3] >> (i & 7)) & 1)
            return res

        l = prime_list(n)
        if len(l) > 0 and l[-1] == n:
            l.pop()
        return len(l)
26256