---

浅谈线性素数筛法

线性素数筛法

基础算法，又名埃拉托斯特尼筛法，先贴代码

//由于 bool 类型的特殊性，可用 memset(p, true, sizeof(p)) 初始化
bool p[maxn];

void prime(int n) {
    memset(p, true, sizeof(p));
	p[1] = false;
	for (int i = 2; i * i < n; i++) {
		if (!p[i]) continue;
		for (int j = 2; i * j <= n; j++) p[i * j] = false;
	}
}

原理很简单，如下：

结论1. 任意大于一的合数一定是某个比它小的素数的倍数（想一想分解质因数的结果）
结论2. 同时我们也可以得出另一个简单的结论，即不能用任何素数(比它小)的非1整数倍表示的数一定是素数

---

那么我们只要从第一个素数 2 开始，把所求范围内它的倍数都打上false的标签，根据结论2，没被打false的 3 也是素数，再把 3 的倍数打上false，下一个数是 4 ，已经被标记，直接跳过，然后遇到没被标记的 5 ，做和对 2、 3 相同的操作，依此类推……直到正在尝试的数大于范围上界的平方根，此时范围内所有的合数都被打上false标签，素数都为true标签，退出循环

至于为什么循环到范围上界的平方根位置位置就可以结束，原因很简单，拿21举例，3×7=21，7×3=21，当尝试的数字超过平方根时，我们的操作就和刚才是恰好“对称”的，该打的标签刚才都打过了，拍屁股走人就好了

这里我们会发现一个问题，2会把6打上标签，3也会把6打上标签，也就是说，在打标签的过程中其实我们是有重复操作的，这就是为什么这个算法的时间复杂度为O(nlglgn)，并不是严格线性的

下面我来讨论一下线性素数筛法的优化

快速线性素数筛法

这个方法也叫欧拉筛，先贴代码，引自洛谷某大佬

bool isPrime[maxn];
int Prime[maxn], cnt = 0;

void prime(int n) {
    memset(isPrime, 1, sizeof(isPrime));
    isPrime[1] = 0;
    for(int i = 2; i <= n; i++) {
        if(isPrime[i]) 
            Prime[++cnt] = i;
        for(int j = 1; j <= cnt && i*Prime[j] <= n; j++) {
            isPrime[i * Prime[j]] = 0;
            if(i % Prime[j] == 0)
                break;
        }
    }
}

首先，让我简单描述一下这段程序干了啥：

1. 开俩数组，$bool$数组放标签，$int$数组升序排列已求的素数

2. 打个$2$到$n$的循环：

   • 如果$i$没被之前的数打过就是素数，录入$Prime$数组
   • 找出$i$的最小质因子与最小质因子之前的所有素数因子$p_j$，在范围内依次把$i×p_j$打上$false$

---

作为一个觉得数论好难的蒟蒻，刚开始想这段代码的时候脑袋晕晕的，让我们意会一下：

欧拉筛与埃拉托斯特尼筛在行为上有一定的相似性，他们都是通过某个质因子去打掉为质因子倍数的合数

埃拉托斯特尼筛直接打倍数，欧拉筛则打“最小质因子之前的质数”倍数

但是，埃拉托斯特尼筛有冗余操作，而欧拉筛完美做到了不重不漏

⭐想完就觉得两种方法似是而非，好像能理解一些了，那么接下来只要能乱搞证明欧拉筛能够不重不漏地打掉所有合数就可以彻底理解它了！

1. 不漏

   这个更简单，对范围内任意一个合数，取$p$为$C$的最小质因子，那么有$C=p×i$

   一个あほ＋ばか的思路：

   $i$的取值范围为$2$到$n$，这个范围的$i$足够构造出所有范围内合数

   另外，因为$p<i$，所以构造任意$C$时素数表里一定已经存在$p$，且一定会枚举到$p$

   那么此$p×i$的组合一定会被枚举到

   伪证毕

2. 不重

   设$C$为范围内合数，$p_1$为其最小质因子，那么一定有$C=p_1×i$ （根据“不漏”）

   那么$C$在循环过程中一定被$p_1×i$的组合筛过

   在筛过后，假设还存在$p_1<p_2<C$，且$C=p_2×j$，使$C$又被$p_2×j$的组合筛去

   $\because p_1为C的最小质因子$

   $\therefore j可被分解为p_1×k，即p_1 \mid j$

   那么在枚举素数产生$p×j$的过程中，一定会先枚举到$p_1$，并且会由于 $j \ mod \ p_1=0$ 停止枚举

   所以根本不会有$p_2$出现的机会，此时与假设产生矛盾

   另外如果$i=p_1$，因为不同$i$只会在循环出现一次，所以不会重

   因此，对于范围内任意一个被筛除的合数，会且只会被其最小因子筛除

   证毕

3. 线性时间复杂度

   因为不重不漏，每个数只会被筛一次，被筛过了就会跳过

   所以显然每个数都只会近似均摊$O(1)$的时间成本

   因此，欧拉筛的时间复杂度是$O(n)$

至此，我已经把欧拉筛已经搞懂了，剩下的就是把算法版子刻在心里了！加油！

如果俺的博客还真有别人在看且对你有帮助的话，评论一下呗|･ω･｀)~

 

起笔2020年新年第一天，落笔2020年1月25号（同一天）

 

标签