<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 {
// public:
//     bool checkForPrime(int num){
//         if(num == 1) return false;
//         if(num == 2) return true;
//         for(int i=2;i<=num/2;i++){
//             if(num % i == 0) return false;
//         }
//         return true;
//     }
//     int countPrimes(int n) {
//         if(n == 0 || n == 1) return 0;
//         int k = 0;
//         for(int i=2;i<n;i++){
//             if(checkForPrime(i)) k++;
//         }
//         return k;
//     }
// };


class Solution{
public:
    int countPrimes(int n){
        vector<bool> vec;
        for(int i = 0;i<=n;i++){
            vec.push_back(true);
        }
        int i = 2;
        while(i*i <= n){
            if(vec[i] == false) {
                cout<<i<<"f ";
                i++;
                continue;
            }
            cout<<i<<"p ";
            for(int j = i;j<=n/i; j++){
                vec[i*j] = false;
            }
            i++;
        }
        int k = 0;
        for(int c=2;c<n;c++){
            if(vec[c] == true) k++;
        }
        return k; 
    }
};
18900