算法基础课笔记（三四）

如果我们想要知道小于等于n有多少个质数呢？

需要质数筛法。

三种筛法参考： https://www.acwing.com/solution/content/7950/。

1.朴素筛法：

(1).做法:把2~(n-1)中的所有的数的倍数都标记上,最后没有被标记的数就是质数。

(2).原理:假定有一个数p未被2~(p-1)中的数标记过,那么说明,不存在2~(p-1)中的任何一个数的倍数是p,
也就是说p不是2~(p-1)中的任何数的倍数,也就是说2~(p-1)中不存在p的约数,因此,根据质数的定义可知:
p是质数。

void get_primes(){
    for(int i=2;i<=n;i++){
        if(!st[i]) primes[cnt++]=i;//把素数存起来
        for(int j=2*i;j<=n;j+=i){//不管是合数还是质数，都用来筛掉后面它的倍数
            st[j]=true;
        }
    }
}

计算时间复杂度：

调和级数：当n趋近于正无穷的时候，1/2+1/3+1/4+1/5+…+1/n=ln n+c，(c是欧拉常数，约等于0.577左右)

内层循环计算次数，$n/2 + n/3 + … + n/n \approx n \star ln n < n \star log_2 n$，所以时间复杂度为：$O(n \star log n)$。

这里Latex公式渲染有问题，两个*会被hexo转义为斜体，所以用\star代替。

2.埃拉托斯特尼筛法：简称埃氏筛法。

我们发现朴素筛存在可以优化的地方，首先它有大量重复标记；其次对于一个数p，判断它是不是质数，由算术基本定理，只需要判断它是不是[2,p-1]中的质数的倍数，而不用判断[2,p-1]中的所有数的倍数，这就是埃氏筛改进的地方。

void get_primes(){
    for(int i=2;i<=n;i++){
        if(!st[i]){
            primes[cnt++]=i;
            for(int j=2*i;j<=n;j+=i) st[j]=true;//可以用质数i就把所有的合数都筛掉
        }
    }
}

质数定理：1~n中有$\frac n {ln n}$个质数。

计算时间复杂度：

内层循环计算次数，$n/2 + n/3 + n/5… + n/[prime]$，时间复杂度为：$O(n*log log n)$。

3.线性筛法：也称为欧拉筛法。

蓝桥杯（三十）中有介绍过欧拉筛法，这里重复一遍。

都叫线性筛了，时间复杂度当然是优秀的O(n)。

参考文章： https://zhuanlan.zhihu.com/p/124068032。

埃氏筛法仍有优化空间，朴素筛法中将一个合数重复多次标记的问题埃氏筛也没有解决。

比如：2和3都是质数，它们都会将合数12标记。

如果能让每个合数都只被标记一次，那么时间复杂度就可以降到$O(n)$了。

在数量级达到n = 10^7时，线性筛会比埃氏筛快1倍左右。

欧拉筛法的核心思想：每个合数只会被它的最小质因子筛掉，所以只会被筛一次。

算法模拟：

s1：建立标记数列（从2到n的自然数）和素数数列；

s2：第一个数字是2（看标记是素数），把素数2放进素数数列，标记2×2为非素数；

s3：第二个数字是3（看标记是素数），把素数3放入素数数列，标记3×2、3×3为非素数；

s4：第三个数字是4（看标记是合数），标记4×2为非素数，break；

s5：第四个数字是5（看标记是素数），把素数5放入素数数列，标记5×2、5×3、5×5为非素数；

……

注意到筛法求素数的同时也得到了每个数的最小质因子。

void get_primes(){
    for(int i=2;i<=n;i++){
        if(!st[i]) primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++){// primes[j]*i<=n,把大于n的合数都筛了没意义
            st[primes[j]*i]=true;//用最小质因子去筛合数
            //1)当i%primes[j]!=0时,说明此时遍历到的primes[j]不是i的质因子，那么只可能是此时的primes[j]<i的最小质因子,所以primes[j]*i的最小质因子就是primes[j];
            /*2)当有i%primes[j]==0时,说明i的最小质因子是primes[j],因此primes[j]*i的最小质因子也就应该是prime[j]，之后接着用st[primes[j+1]*i]=true去筛合数时，就不是用最小质因子去更新了,因为i有最小质因子primes[j]<primes[j+1],此时的primes[j+1]不是primes[j+1]*i的最小质因子，此时就应该break*/
            // ！！！关键步骤：退出循环，避免之后重复进行筛选，保证只被最小质因子筛掉
            if(i%primes[j]==0) break;
        }
    }
}

为什么要break？

避免i*primes[j+1]被提前筛掉，满足if条件，i*primes[j+1]的最小质因子就是primes[j]，如果不退出它就会被primes[j+1]筛掉，会重复。

比如12有两种分解方式：4*3和6*2，在4 % 2 == 0的时候就知道了4的最小质因子是2，所以4*3的最小质因子也是2，必须退出，直到6*2用最小质因子2筛掉它。

primes[j]*i取决于两者，看primes[j]和i谁的最小质因子更小，代码注释中已经解释了2种情况。

欧拉筛法可以顺便求出primes[j]*i的最小质因子primes[j]。

4.其他筛法优化技巧：

只筛奇数，

因为除 2 以外的偶数都是合数，所以我们可以直接跳过它们，只用关心奇数就好。

首先，这样做能让我们内存需求减半；其次，所需的操作大约也减半。

5.总结：

筛质数一般用线性筛法就行，埃氏筛法不怎么用但是思想还是很有用。

例题：868. 筛质数（模板题）

给定一个正整数 n，请你求出 1∼n 中质数的个数。

输入格式
共一行，包含整数 n。

输出格式
共一行，包含一个整数，表示 1∼n 中质数的个数。

数据范围
1≤n≤10^6
输入样例：
8
输出样例：
4

算法1：朴素筛法。

#include <iostream>
using namespace std;
const int N = 1e6+6;
bool st[N];
int n;

int main(){
    
    cin >> n;
    
    int cnt = 0;
    for (int i = 2;i <= n;i ++){
        if (!st[i]) cnt ++;
        for (int j = 2*i;j <= n;j += i) st[j] = true;
    }
    
    cout << cnt;
    return 0;
}

算法2：埃氏筛法。

#include <iostream>
using namespace std;
const int N = 1e6+5;
bool st[N];

int main(){
    int n;
    cin >> n;
    
    int cnt = 0;
    for (int i = 2;i <= n;i ++){
        if (!st[i]){ 
            cnt ++; // 对朴素筛法的改进，只通过质数筛掉合数，避免重复筛选
            for (int j = 2*i;j <= n;j += i)
                st[j] = true;
        }
    }
    
    cout << cnt;
    return 0;
}

算法3：线性筛法。

#include <iostream>
using namespace std;
const int N = 1e6+5;
int n;
bool st[N];
int primes[N];

int main(){
    cin >> n;
    int cnt = 0;
    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;
        }
    }
    cout << cnt << '\n';
    return 0;
}