204.计数质数
题目来源：https://leetcode-cn.com/problems/count-primes/
统计所有小于非负整数 n 的质数的数量。
示例 1：
输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2：
输入：n = 0
输出：0
示例 3：
输入：n = 1
输出：0
提示：
0 <= n <= 5 * 10^6
解法
方法一：暴力枚举法
暴力枚举，判断一个数n是否为素质，仅需判断sqrt(n)之前的数能否被判断的数整除即可。
C++代码如下
class Solution {
private:
bool isPrime(int n){
for(int i=3;i*i<=n;i+=2){
if(n%i==0) return false;
}
return true;
}
public:
int countPrimes(int n) {
if(n<3){
return 0;
}
int i,j,cnt=1;
for(i=3;i<n;i+=2){
if(isPrime(i)){
cnt++;
}
}
return cnt;
}
};
复杂度分析：
时间复杂度：O(n*sqrt(n))
空间复杂度：O(1)
方法二：埃拉托斯特尼筛法
埃拉托斯特尼筛法：要得到自然数n以内的全部素数，必须把不大于sqrt(n)的所有素数的倍数剔除，剩下的就是素数。使用一个bool型数组来维护指定数是否为素数，初始该数组全为true，即假定所有数均为素数。每次根据bool数组结果判断是否为素数。当该数<=sqrt(n)且为素数时，将bool数组下标为该数倍数的置为false ，即剔除合数。
实现代码如下：
class Solution {
// 埃拉托斯特尼筛法
public:
int countPrimes(int n) {
bool *isPrime = new bool[n+1];
for(int i=0;i<=n;i++){
isPrime[i]=true;
}
int cnt = 0;
for(int i=2;i<n;i++){
if(isPrime[i]){
++cnt;
if((long)i*i<=(long)n){ // 剔除素数倍数
for(int j=i << 1;j<=n;j+=i){
isPrime[j] = false;
}
}
}
}
return cnt;
}
};
复杂度分析：
时间复杂度：O(nloglogn)
空间复杂度：O(n)
