概述
在数学的王国里，质数（也即素数）是数这个范围内一枚闪闪发光的重要宝石，很多公式和定理都与素数有关。这样，如何判断一个数是否是素数也是一个重要的问题，只不过这个问题的解法相当显而易见，那么我们的目光就要更多的放在对于判断素数的算法的性能的优化上了（更多的是时间复杂度）。
有关质数的定义和性质在这里就不过多阐述了，我在本篇文章中主要讲解三种素数筛法，分别是朴素筛，埃筛以及欧筛（再有别的我就不知道了……菜的我）。
正文
朴素筛
平时大家最常用的应该就是朴素筛了，这种筛法的原理依赖于素数的定义：在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。这样就衍生出了一种判断素数的方法，即把当前需要判断的数n作为被模除数，用n不断从2开始到n-1尝试模除，如果结果等于0，代表可以整除，即也代表该数除了1与它本身有其他因数，故不符合素数定义，达到判断素数的功能。
原理论证
朴素筛的原理在上面大概讲清楚了，在这里我们主要论证两个问题。一个是从模除（2n-1）优化到模除（2sqrt(n)）的原理，还有就是对于朴素筛的时间复杂度的估算（虽然很简单）。
这里先摆出一段判断2n所有数是质数还是合数的核心代码（模除2i-1）
a数组中0代表该数是合数、1代表该数是质数
for(int i=2;i<=n;i++)
{
for(int j=2;j<=i-1;j++)
{
if(i%j==0)
{
a[i]=0;
break;
}
}
}
a数组在一开始都被赋了1为初值，代表所有数在未判别之前默认是质数（1除外，1另外赋值为0，因为不需要判断），当i（待判断数）能够整除j，则说明j是i的一个非1非本身因子，也即说明i不是一个质数，就可以赋值为0，不需要再向下进行尝试了。
通过这里很明显可以得出大概时间复杂度为O(N^2)。
再看一段经过优化的核心代码（模除2~sqrt(i)）
for(int i=2;i<=n;i++)
{
for(int j=2;j<=sqrt(i);j++)
{
if(i%j==0)
{
a[i]=0;
break;
}
}
}
这段代码的时间复杂度很明显也可以得出大概为O(N√N)。
现在我们来论证一下这个小优化的正确性。
首先我们可以看出来，这么优化造成的结果是不再尝试模除（sqrt(i)~i-1）区间的数。那么，不尝试这些数会不会对最终的判断结果造成什么影响呢？
我们知道sqrt(i)×sqrt(i)的结果就是i，那么当一个数x>sqrt(i)时，如果i%x==0，那么在2~sqrt(i)这个区间内一定有一个数k，能够使得i%k==0，因为k×x等于i。这样，在后面的区间内，如果存在i的非1非本身因子，则在前面的区间里，也存在这样一个因子，所以不需要遍历后面的区间了。
另外，我遇到过有一些题目，会对这个小优化的时间复杂度进行限制，不用的话会TLE。
代码实现
#include<stdio.h>
#include<math.h>
int main()
{
int n; //假定5000以内
int a[5005];
scanf("%d",&n);
a[1]=0;
for(int i=1;i<=n;i++)
{
a[i]=1;
}
for(int i=2;i<=n;i++)
{
for(int j=2;j<=sqrt(i);j++)
{
if(i%j==0)
{
a[i]=0;
break;
}
}
}
for(int i=1;i<=n;i++)
{
printf("%d\n",a[i]);
}
return 0;
}
在这里我是用了一个数组来记录所有数是质数还是合数，但是在实际题目中，这个需求会有很多种，常见的可能会输出质数表或者判断某个数是否是质数，这可以视题目要求再进行具体变化。
埃筛
埃筛是埃拉托斯特尼筛的简称，又叫(Eratosthenes筛)。是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。（百度百科）
埃筛通过提前标记质数的倍数为合数避免了很多数的判断，相当于利用了质数的性质进行了算法的优化，成功的降低了时间复杂度。
原理论证
我们在放出代码之后再进行埃筛的时间复杂度分析，现在这里主要来论证埃筛的大致原理以及埃筛内容中的一点小优化。
正如上面所说，埃筛的思想大概就是利用了质数不能有非1非本身其他因子的出现，而质数的倍数一定是一个合数这个性质（其实合数的倍数也是合数，但是合数的倍数会在之前被标记到），避免了外部循环遍历到该质数时的朴素判断。
原理上来说，我们仍然在一开始假定所有数都是质数，从2开始，对2的所有小于n的倍数进行标记，标记它们为合数，在之后的遍历中，如果遍历到合数则无需再次判断，也不需要再标记该合数的倍数（因为该合数的倍数一定也是标记这个合数的质数的倍数，一定也已经被标记过了）。而遍历到3时，3没有被标记为合数，则需标记3的倍数······
标记的结果如下图所示，1既不是质数也不是合数，所以用黑色涂满。2、3、5、7的倍数分别用蓝色、橙色、绿色、紫色来涂满。剩下的白色的数代表质数。
那么这里有一个问题，我们可以直观地看出3是个质数，它被筛过理所应当，但是有没有合数被错误的筛过呢？
我们现在假设一个数x为合数，而x一定存在至少一个非1非本身因数a（可能两个因数相同）。假设a本身是个合数，则它与x本质上没有区别，仍然至少存在一个非1非本身因数。而假设a本身是个质数，则该合数就已经被标记。而假如该数a是合数，a因数也是一个合数，也不过是将这个判断过程不断传递下去，最终会在一个无法被分成合数×合数的节点上变成质数×质数或者是质数×合数。总归是会被一个质数标记的，这样子就证明了埃筛理论上的严谨性与健壮。
现在我们来说一点小优化
埃筛的基础思想是对质数的倍数进行标记，我们很容易就可以在前几个质数中发现重复判断的数（如上图所示红圈圈出来的），在2的倍数时，2×3=6需要被标记，但是在3的倍数时，3×2=6也需要被标记一次，这里就造成了重复判断，而随着n的增大，这样的重复判断会越来越多，造成时间浪费，所以，这里衍生出了一种巧妙地小优化。就是在对i的倍数进行标记时（假设i已经是个质数），从i×i开始判断，即从i的i倍开始判断。
那么这么优化到底有没有道理呢？我们来看一看。
对于3×2（3的2倍）需要打标记这次判断，3的2倍也同样是2的3倍，就不用再进行判断了，故i=3时，可以从i本身也就是3倍开始进行标记。有的读者可能会说，这是两个质数相乘，那如果一个质数和一个合数相乘呢？（不要说两个合数，动动脑子）。我们来看，首先，不可能遍历到一个合数然后标记该合数的质数倍（前面已经说明了）。所以，如果出现这种情况，那一定是遍历到一个质数然后标记该质数的合数倍，我们举个例子。假设遍历到5，此时应该标记5×4=20这个数为合数，那么在之前，这个数有没有被标记过呢？
显而易见，20是2的倍数，被标记过了。那20被标记的过程是怎么样的呢？20作为一个合数4的倍数，也是标记4的质数2的倍数，所以在遍历2时就会被标记，所以质数和合数相乘时，从i×i开始记录也是有所证明的。
还有一个小优化也就是在一开始百度百科中说的那样，只需要去标记不大于根号n的所有素数的倍数，这样做也是有实际理论依据的。刚刚我们已经证明了对于一个质数i，从i×i开始标记的正确性，那么对于一个大于根号n的质数j，我们不标记它的倍数会不会有问题。
事实上是不会的，因为j×j必然大于n，不需要判断。
代码实现
#include<stdio.h>
#include<math.h>
int main()
{
int n;
int a[5005];
scanf("%d",&n);
for(int i=2;i<=n;i++)
{
a[i]=1;
}
a[1]=0;
for(int i=2;i<=sqrt(n);i++)
{
if(a[i]==1) //如果是质数
{
for(int j=i*i;j<=n;j+=i)
{
a[j]=0;
}
}
}
for(int i=1;i<=n;i++)
{
printf("%d=%d\n",i,a[i]);
}
return 0;
}
时间复杂度分析
埃筛的时间复杂度很神奇的是O(nloglogn)，我们一般看到的时间复杂度都是O(n),O(n^2),O(logn)，几乎很少看到这种时间复杂度。
看到之后我就去网上搜关于欧筛的时间复杂度的证明，也算是找到了几个。
我把地址放在下面，正确性不明确（我也没证，只是简单的看了看），有兴趣的读者可以自行证明。
https://blog.csdn.net/Gavin_Nicholas/article/details/88974079
https://blog.csdn.net/OIljt12138/article/details/53861367
在这里膜拜两位大佬。
欧筛
欧筛是欧拉筛的简称，也叫（Euler筛），又叫线性筛，时间复杂度达到O(n)而得名。
欧筛是埃筛的优化版本，在埃筛的介绍中，我们提到了埃筛的重复判断以及埃筛的小优化，但是埃筛本身的小优化并不能够完全去除重复筛选，只能去除两个因数相同的判断，对于因数不同的两次判断便无能为力了。我们来看12这个数。12=3×4=2×6，也就是说12这个数在埃筛中，会作为2的6倍筛一次，又会作为3的4倍筛一次，埃筛本身没有处理这个问题，于是引出了欧筛。
欧筛本身的思想是对于每个合数，只筛最小质数的倍数那一次。
原理论证
欧筛的思想没有什么新的思路需要证明，就在这里讲解一下欧筛的实现过程。
欧筛的思想很好理解，但是代码实现不算很简单，需要作出一定思考：如何才能做到，永远只用最小质数筛合数。
其实如果能想到这点就能想到，每次对于某一个数来说，如果这个数是质数，就把它记在一个数组里，做成一个素数表，用以查找。遍历每一个数i，让这个数i作为对之前所记录的所有质数的倍数来求得某一个质数的所有倍数。乍看起来好像并不严谨，但仔细思考之后会发现，这跟埃筛的i×i开始有异曲同工之妙，而且这样做还可以方便的对于每一个数去遍历质数表，找到这个数的最小质因数，从而停止对该合数的多余判断。
假如i%prime[j]==0，那么j这个位置放的质数就是i的最小质因子了，prime[j+1]没有再去乘i的必要了。（prime数组是质数表）
可以先尝试阅读代码，代码下面有图解。
代码实现
#include<stdio.h>
#include<math.h>
int prim[5005];
int num=0,sum=0;
int a[5005];
int main()
{
int n;
scanf("%d",&n);
for(int i=2;i<=n;i++)
{
a[i]=1;
}
a[1]=0;
for(int i=2;i<=n;i++)
{
if(a[i]==1)
{
num++;
prim[num]=i;
}
for(int j=1;j<=num;j++)
{
sum++;
if(i*prim[j]>n)
{
break;
}
a[i*prim[j]]=0;
if(i%prim[j]==0)
{
break;
}
}
}
for(int i=1;i<=n;i++)
{
printf("%d=%d\n",i,a[i]);
}
printf("%d",sum);
return 0;
}
虽然代码是我自己后来打的，但是大概还是先看了一篇博客的讲解，在这里给出这篇博客的地址。
https://www.jianshu.com/p/2031036dba4b
总感觉欧筛还有别的实现方法，但在此先只说这一种吧，如果过后有所发现再补充。
时间复杂度分析
欧筛的时间复杂度众所周知O(n)（不然为啥叫线性筛啊）。
可以很明显看出来，对于每一个数，都只判断了一次，也即对于每一个数，时间复杂度是O(1)。
欧筛拓展(ge pi)
跟欧筛有关的还有一个欧拉函数
欧筛求素数表可以直接求得欧拉函数
在数论，对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目（因此φ(1)=1）。此函数以其首名研究者欧拉命名(Euler’s totient function)，它又称为Euler’s totient function、φ函数、欧拉商数等。 例如φ(8)=4，因为1,3,5,7均和8互质。 从欧拉函数引伸出来在环论方面的事实和拉格朗日定理构成了欧拉定理的证明。
————百度百科
（具体的没咋看，过段时间再看，先到这里吧）
其他筛法
其实这些天在准备这篇博客的时候，也有看到很多别的筛法，就不举例子了，在这里只列举了三种最常见的筛法吧。
小结
好多天没有写博客了，这些字基本上一个上午码出来的，但是事先的查资料，捋顺思路还是花了一些时间，可能是最近心思没在这些上面吧，后面会慢慢回来。
筛法大多是模板题，正式比赛筛法也基本上是作为预处理出现的，预处理的话总感觉朴素筛用处不大（因为谁都知道），不过总的来说，练习的话，模板题也够了。
Author: Maple
Link: http://www.unknown9t.com/2022/04/29/%E5%B8%B8%E8%A7%81%E7%B4%A0%E6%95%B0%E7%AD%9B/
Copyright: All articles in this blog are licensed under CC BY-NC-SA 3.0 unless stating additionally.