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

int SIZE = 5e6; // max(num)
int maxPrimeSize = SIZE + 1; //should be larger than max value
vector<bool> isPrime(maxPrimeSize + 1, true);
vector<int> prefixPrimeCount(maxPrimeSize + 1);
vector<int> primeTable;
auto sieve = [] {
	if (maxPrimeSize < 0) {
		return 0;
	}
	if (maxPrimeSize == 0) {
		isPrime[0] = false;
		return 0;
	}
	isPrime[0] = isPrime[1] = false;
	if (maxPrimeSize == 1) {
		return 0;
	}
	int sqrt_size = sqrt(maxPrimeSize);
	// maxPrimeSize = sqrt_size;
	// if we don't need primeTable, we can use only sqrt_size
	// that can reduce time complexity to sqrt(N)loglog(sqrt(N))
	// if we need primeTable, we would use [2, maxPrimeSize]
	// time: O(Nloglog(N))
	for (int i = 2; i <= maxPrimeSize; i++) {
		if (isPrime[i]) {
            prefixPrimeCount[i] = prefixPrimeCount[i - 1] + 1;
			primeTable.push_back(i);
			for (long long j = (long long)i * i; j <= maxPrimeSize; j += i) {
				isPrime[j] = false;
			}
		}
        else {
            prefixPrimeCount[i] = prefixPrimeCount[i - 1];
        }
	}
	return 0;
}();
class Solution {
public:
    int countPrimes(int n) {
        return prefixPrimeCount[max(0, n - 1)];
    }
};
32940