题目

题解

1. 暴力法

直接用暴力法会超时，时间复杂度$O(n^{2})$，因此使用暴力法要进行优化，即isPrime()函数只用遍历到sqrt(N)，因为：
$$ 2 × 6 = 12\\
3 × 4 = 12\\
sqrt(12) × sqrt(12) = 12\\
4 × 3 = 12\\
6 × 2 = 12\\
$$ 可以看出从sqrt(12)开始上下的对称的，那么sqrt(12)上面若没找到因数，则下面也没有

  • 时间复杂度$O(sqrt(n)*n)$
  • 空间复杂度$O(1)$
class Solution {
public:
    //0和1不是质数
    bool isPrime(int n){
        for(int i=2; i*i<=n;++i){//注意只要搜索到sqrt(n)就可以，因为在sqrt(n)前后是对称的，见提示3
            if(n%i==0) return false;
        }
        return true;
    }
    int countPrimes(int n) {//两个方法。1暴力法
        int res = 0;
        for(int i=2; i<n; ++i){
            if(isPrime(i)) res++;
        }
        return res;
    }
};

2. 埃拉托斯特尼筛法

用一个vector存小于n的所有数是否为质数，然后挨个筛，从2开始，2的倍数全为合数，筛掉，然后3的倍数，遇到合数就不求倍数，具体看这个图：


来源wikipedia

  • 时间复杂度$O(nlog{log{n}})$
  • 空间复杂度$O(n)$
class Solution {
public:
    //0和1不是质数
    int countPrimes(int n) {//两个方法。2埃拉托斯特尼筛法
        int res = 0;
        vector<bool> prime(n-1, true);
        for(int i=2; i<n; ++i){
            if(!prime[i]) continue;
            res++;
            for(int k=2; k*i<n; ++k){
                prime[i*k] = false;
            }
        }
        return res;
    }
};

其他

另外还有欧拉筛法，Sundaram筛法等待等,时间复杂度更低，理解起来相对更复杂一点，这里先记录，有空好好研究完善素数筛法
详见(https://bruceking.site/2017/09/18/prime-sieves/)和(https://www.cnblogs.com/grubbyskyer/p/3852421.html)