质数也叫素数,只能被1和它本身整除的。
利用筛选法。
class Solution {
public:
int countPrimes(int n) {
if(n < )
return ;
int result = ;
vector<bool> isPrime(n+);
for(int i=;i<isPrime.size();++i)
isPrime[i] = true;
isPrime[] = false;
isPrime[] = false;
for(int i=;i<n;++i)
{
if(isPrime[i])
{
result++;
for(int j=i*;j<n;j+=i) # 去除i的倍数
isPrime[j] = false;
}
}
return result; }
};