204. 计数质数（素数筛）-526互联

给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。

示例 1：

输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

示例 2：

输入：n = 0
输出：0

示例 3：

输入：n = 1
输出：0

先上本题做法：（直接用2到sqrt的是过不了的，数据上来就会超时，本题采用欧拉筛，后面会介绍几种求质数的方法）

static bool is_not_p[5000001]; //偷懒写法，因为static在内存中自动用0填充，如果多次运行一定记得初始化为0
vector<int> primes;
class Solution {
public:

    void isPrime(int num){
        for(int i=2;i<=num;i++){
            if(!is_not_p[i]){
                primes.push_back(i);
        //        cout<<i;
            }
            for(int p : primes){
                if(p*i>num) break;
                is_not_p[p*i]=true;
                if(i%p==0) break; //保证被最小因数筛掉，每个数会且只会被筛一遍
            }
        }
    }
    int countPrimes(int n) {
        int ans=0;
        isPrime(n);
        
        for(int i=2;i<n;i++){
            if(!is_not_p[i]) 
            {
             //   cout<<i<<endl;
                ans++;
            }
        }
        return ans;
    }
};

介绍一下几种素数筛：

一、埃氏筛法

首先将2到n范围内的所有整数写下来。其中最小的数字2是素数。将表中所有2的倍数都划去。表中剩余的最小数字是3，他不能被更小的数整除，所以3是素数。再将表中所有3的倍数都划去。如果表中剩余的最小数字是m时，m就是素数。然后将m的倍数都划去。依次类推，反复操作，就能依次枚举出n以内的素数在这里插入图片描述

时间复杂度：

O(n*log(logn))

代码如下：

int prime[MAXN];//第i个素数
bool is_prime[MAXN+1];//is_prime[i]为true时表示i为素数

void init(){
    int p=0;
    for(int i=0;i<n;i++){
        is_prime[i]=true;
    }
    is_prime[0]=is_prime[1]=false;
    for(int i=2;i<=n;i++){
        if(is_prime[i]){
            prime[p++]=i;
            for(int j=2*i;j<=n;j+=i){
                is_prime[j]=false;
            }
        }
    }
}

二、区间筛法

如：在区间[a,b)内有多少个素数素数判定中，如果d是n的约数，那么n/d也是n的约数。由n=d * n / d可知min(d,n/d)<=

n\sqrt{n}n​,所以只需要检查2~n\sqrt{n}n​就行了，故而有b以内的合数的最小质因数一定不超过b\sqrt{b}b​。 如果有b\sqrt{b}b​内的素数表的话，就可以把埃氏筛法应用到[a,b)上。也就是说，先分别做好[2,b\sqrt{b}b​)的表和[a,b)的表，然后从[2,b\sqrt{b}b​)的表中筛得素数的同时，也将倍数从[a,b)的表划去，剩下的就是[a,b)内的素数了

时间复杂度：

O(n√n)

代码如下：

typedef long long ll;

bool is_prime[MAXN];//is_prime[i-a]=true <=> i是素数
bool is_prime_small[MAXN];

//对区间[a,b)内的整数筛选素数。
void segment_sieve(ll a,ll b){
    for(int i=0;(ll)i*i<b;i++)	is_prime_small[i]=true;
    for(int i=0;i<b-a;i++)	is_prime[i]=true;
    
    for(int i=2;(ll)i*i<b;i++){
        if(is_prime_small[i]){
            //筛[2,根号b)
            for(int j=2*i;(ll)j*j<b;j+=i)	is_prime_small[j]=false;
            //筛[a,b)
            for(int j=max(2LL,((a+i-1)/i)*i;j<b;j+=i)	is_prime[j-a]=false;
        }
    }
}

三、欧拉筛法（线性筛法）

欧拉筛，也叫线性筛，可以在 O（n）时间内完成对2~n的筛选。它的核心思想是：让每一个合数被其最小质因数筛到。

感觉欧拉筛法和埃氏筛法的原理类似…但是欧拉筛法更减少了没有必要的计算，就是增加了处理：每一个被筛掉的数都必须是被它的最小质因子筛掉，为了保证这一点，增添了如下代码：

if(i % prime2[k] == 0)//确保是最小质因数
{
    break;
}

时间复杂度：

O(n)

完整的算法代码如下：

bool isnp[MAXN];
vector<int> primes; // 质数表
void init(int n){
    for (int i = 2; i <= n; i++){
        if (!isnp[i])
            primes.push_back(i);
        for (int p : primes){
            if (p * i > n)
                break;
            isnp[p * i] = 1;
            if (i % p == 0)
                break;
        }
    }
}

也可以：

const int N = 1000010;
int primes[N], cnt=0;  // primes[0]~primes[cnt-1]存储的是0~n中所有的质数(从小到大)
bool st[N];  // st[i] == true说明i不是质数
// 线性选法，时间复杂度：O(n)
void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] <= n / i; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

参考：

https://juejin.cn/post/7085310292237762574

https://juejin.cn/post/7129079647928582175