.png?table=block&id=e721439b-67f8-4fde-8e9a-291fca4d6796&cache=v2)
说到素数，算是老本行了，今天写到一道并查集的时候要求两个数的公约数需要用到质因子。然后就有讨论欧拉筛与埃式筛的复杂度的回答了。想起来自己也基本上忘记这两种筛法的写法了原理，就重新捡起来看了一遍。还是重新记录一下吧。
暴力
首先按照最朴素的写法，如果我们要求得n以下所有的素数，那么最简单的写法是两重循环，直接对小于当前值的每个数求模。但是这种显而易见的很慢。
埃式筛
而埃式筛则更进一步，原理是这样的，每一个数，如果有若干个因子，一定都能把这些因子分解为若干个质因子。这是几乎无需证明的内容，因为每一个非质因子就一定存在更小的质因子。于是，我们可以直接将每个质因子的倍数标记为合数，而每个被遍历到的值且未被标记的则为质数。代码大致如下：
for(int i = 2 ; i <= n ; i ++){
if(prime[i]==0){
for(int j = i*2 ; j <= n ; j +=i){
prime[j]=1;
}
}
}然而这种方式，相比暴力写法，也几乎没有多少优化，所以这个写法还可以更简化。简化的原理是里层的循环由于每一次都是从i*2开始到n结尾，其中重复计算了很多次。例如3*2之前会被2*3筛一遍，所有小于当前值i的合数，其实都已经被筛过一次了。所以我们只需要从j=i*i开始，于是可以得出，外层循环只需要让i*i≤n即可，因为如果大于的话里层循环也根本不会动。代码如下：
for(int i = 2; i <=n/i ; i ++){
if(prime[i]==0){
for(int j = i*i ; j <=n ; j +=i){
prime[j] = 1;
}
}
}欧拉筛
但即使这样也还有优化的办法。欧拉筛的原理每个合数都只由这个数的最小质因子/最大因子来筛除。对于每一个合数来说我们筛除的数列大概是这样算的：2*p,3*p……k*p（p为质数,k*p≤n）
而我们枚举的过程中，刚好会用到2，3，，，n这样的一个数列，而我们每一次循环的时候都将所有乘积为i*(prime[0]~prime[cnt-1])的所有合数排除。这样我们可以保证每个p都经历了从i=2到i=k的过程。
而当st[i]为0是直接选取i为质数的原理大概是：i*(prime[0]~prime[cnt-1])>i+1（i≥2，prime[0~cnt-1]≥2)，在这个等式里i+1的是否为合数的结果一定被前一次的遍历所覆盖，所以可以直接根据st的内容决定i是否为质数。
换一种说法，i+1的所有因子，一定已经经历过i和j的循环了，例如14的质因子为2和7，这在14以前的遍历里早就在i=7，prime[0]=2的时候判断过一次了。
而这里的跳出条件就对应了前面的每个合数都只由他的最小质因子/最大因子排除，因为如果满足条件则有：
这也是为什么我们需要设置这个条件跳出循环，为了保证每个数都只由它的最小质因子prime[j]/最大因子i排除。这样可以最小化循环次数，让时间复杂度几乎为线性。
int prime[n];
int cnt = 0;
prime[cnt++]=2;
int st[n+1];
for(int i = 2 ; i <= n ;i ++){
if(st[i] == 0)prime[cnt++] = i;
for(int j = 0 ; prime[j]*i<=n ; j ++){
st[prime[j]*i] = 1;
if(i%prime[j]==0)break;
}
}总结一下，这两种筛法其实都是由不断将质因子的倍数设为合数演化来的，不同的是埃式筛难免还是会存在一些重复的筛除，而欧拉筛每个数都只会设置一次，所以时间复杂度几乎是线性的。这两种筛法也很好的表达了为了达到某种目的的算法在数论上的优化过程，实际上使用上来说，只要n不是太大，其实都差不多….再提一嘴，更大的素数则要用特别的方法判定了，我记得是叫miller-rabin，不过即使是算法领域也用的很少，可能某些加密算法里会用到，我也早就忘记写法了…等哪天遇到了再重新记录一遍吧。