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)