class Solution {
public:
int countPrimes(int n) {
vector<bool> isPrime(n, true);
int ret = 0;
for (int i = 2; i * i <= n; i ++)
{
if (isPrime[i])
{
for (int j = i * i; j <= n; j += i)
{
isPrime[j] = false;
}
}
}
for (int i = 2; i < n; i ++)
{
if (isPrime[i])
{
ret ++;
}
}
return ret;
}
};
C++ solution based on Sieve of Eratosthenes theory


@liuauto No, equal sign is indispensable, suppose some square number like 9, 16, 25...