Example:
​
Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

class Solution {
vector<int> prime ={2,3,5,7,11};
bool isPrime(int n)
{
    // for( int k=2;k<=sqrt(n);k++)
    for(int k=0;k<prime.size();k++)
    {
        if(prime[k] > sqrt(n)) break;
        if(n%prime[k] ==0) return false;
​
    }
    return true;
}
public:
    int countPrimes(int n) {
        if(n<=prime[prime.size()-1])
        for(int i=0;i<prime.size();i++)
            if(n<=prime[i]) return i;
        for(int k = prime[prime.size()-1]+2 ; k<n; k+=2)
        {
            if( isPrime(k)) prime.push_back(k);
        }
        // for(auto i: prime)
        // cout<<i<<" ";
        return prime.size();
​
    }
};