class Solution {
public:
int countPrimes(int n) {
if(n<3)
return 0;
if(n==3)
return 1;
vector<int> prime;
prime.push_back(2);
for(int i=2; i<n; i++)
{
bool isprime = true;
for(auto j : prime)
{
if(i%j==0)
{
isprime = false;
break;
}
else if(i<j*j)
break;
}
if(isprime)
prime.push_back(i);
}
return prime.size();
}
};
c++ 780ms solution (easy to understand)


@windsound2010 We need to count the number of prime numbers that < n, not <= n, so it seems strange. However, it is right. Thanks.