<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:
    PRIMES = [2, 3, 5, 7, 11, 13]

    def countPrimes(self, n: int) -> int:
        lower, upper = 0, len(self.PRIMES)
        while lower < upper:
            i = (lower + upper) // 2
            if self.PRIMES[i] < n:
                lower = i + 1
            else:
                upper = i
        
        if upper < len(self.PRIMES):
            return upper

        prime = self.PRIMES[-1]
        while prime < n:
            # Generate next prime number
            is_prime = False
            while not is_prime:
                prime += 2
                for d in self.PRIMES:
                    if d ** 2 > prime:
                        is_prime = True
                        break
                    if prime % d == 0:
                        break
            
            self.PRIMES.append(prime)

        return len(self.PRIMES) - 1
                
                    
19818