线性筛素数模板luoguP3383

对于筛素数问题（即给定一个整数N，求出1～N之间的所有质数，称为质数的筛选问题），我们有一些朴素的算法，比如说枚举法（时间复杂度很高，不推荐），以及埃拉特斯特尼筛法（时间复杂度为O(n loglog n），效率接近线性，但是n过大时会TLE），现在我还有两种筛法，一种是快速线性筛（时间复杂度为O(N)），还有一种是我一年前写出来的（也可能是从哪个题解里看的）玄学算法，在洛谷实测比快速线性筛快（原因下面介绍），下面分别介绍。

一、埃拉特斯特尼筛

先贴代码（由于该算法简明易懂，在此仅贴核心代码）。

void primes(int n){
	memset(v,0,sizeof(v));//v数组用于标记合数，首先清零
	for(int i=2;i<=n;i++)
	{
		if(v[i])continue;//i是合数
		for(int j=i;j<=n/i;j++)//如果i是质数，标记其倍数，用加法是因为加法在理论上比乘法稍快点 
		 v[i*j]=1;
	 } 
}

这是在数据范围要求不高的情况下进行的筛法，其正确性证明可自行百度。但是根据代码可知，埃拉特斯特尼算法中有一个明显的缺陷，在于筛合数时会对某些合数进行重复标记，就是比如说我们筛12时，2*6筛了一次，3*4筛了一次，重复筛除增加了时间复杂度，在竞赛时数据过大可能会造成超时，于是我就使用以下算法进行改进。

二、埃拉特斯特尼改进玄学筛

依旧先贴代码。

#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
bool a[100000001];
int m,n,s;
int main()
{
    scanf("%d%d",&m,&n);
    int f=sqrt(m);
    a[1]=1;
    for(int i=4;i<=m;i+=2)  a[i]=1;
    for(int i=3;i<=f+1;i++) 
    {
      if(a[i]==0)//i是质数
      {
        for(int j=i*i;j<=m;j+=i)//倍乘筛合数
        a[j]=1;	
      }
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&s);
        if(a[s]==0)
        printf("Yes\n");
        else
        printf("No\n");
    }
    return 0;
}

先插几句，看到这个我一年前的程序记录的数据简直震惊，因为在洛谷上这种玄学筛法比下面的标准线性筛法快！如下图所示

玄学筛

快速线性筛

于是我细细研究我这一年前的脑洞。

首先这个算法和埃拉特斯特尼算法的思想是一致的，但是最大的改进之处在于这个算法把n的循环缩减到了根号n，我们可以知道，在1～N的区间内的每一个合数，都一定有一个约数<=根号N，证明很简单，因为每一个合数x，都一定有一个约数<=根号x；而又因为x<=n，所以根号x<=根号n，所以可得出该结论。这样就把O(n loglog n）的时间复杂度缩减到了O(根号n loglog n）（应该是吧）。

我一度以为这个时间复杂度强于O(N)的快速线性筛，于是去请教学（da）长（lao) dkw，hzy，lml等，经过指点后认为应该是洛谷的数据太水了，于是自行测试了筛1～100，000，000区间内的素数所需的时间。结果如下。

结果很明显了，玄学筛确实要比快速线性筛的速度慢得多，果然还是洛谷数据太水，仔细查看代码，发现我的快速线性筛是先将最大范围内的素数筛出来，不管题目给的范围，所以在小数据下当然就比灵活的玄学筛慢得多。毕竟它是线性，速度理应更快，所以我们在下面就介绍一下这种经典筛法。

三、快速线性筛

还是先贴代码。

#include<cstdio>
#include<cstring>
using namespace std;
#define M 10000100
int  prime[M];
int primes;
bool com[M];
void solve(long long n){
    primes=0;
    memset(com,false,sizeof(com));
    com[0]=com[1]=true;//1不是质数也不是合数，需要特判 
    for(int i=2;i<=n;++i)
    {
        if(!com[i]) prime[++primes]=i;//是质数，就存入prime数组，并将计数器+1 
        for(int j=1;j<=primes&&i*prime[j]<=n;++j){
            com[i*prime[j]]=true;//标记合数，用质数乘该数 
            if(!(i%prime[j]))//若该数可被当前质数整除，则说明不必再继续乘，可枚举下一个质数 
                 break;
        }
    }
}
int main(){
    solve(M);
    int n,m;
    scanf("%d%d",&n,&m);
    while(m--){
        int xx;
        scanf("%d",&xx);
        if(com[xx]==true) printf("No\n");
          else printf("Yes\n");
    //    printf("%d\n",prime[xx]);
    }
}

为了避免埃拉特斯特尼筛重复标记合数的问题，我们可在此运用一种确定出唯一的产生合数的方式，那就是在生成一个需要标记的合数的时候，每次只向现有的数中乘上一个质因子，并让这个质因子是这个合数的最小质因子。这样就可以让每个合数只有一种产生方式。核心代码是solve的那一段。较难以理解的是break那一段，为什么当i可以整除当前数时就要退出？这和该算法的目的有关。当i第一次可以整除prime[j]时，即第一个搜到了i的最小质因子，同时也是要下一次标记的合数(即prime[j+1]*i)的最小质因子，如果进行下一次标记，那么就不符合乘上的质因子是需要标记的合数的最小质因子（即如果标记prime[j+1]*i，那么prime[j+1]*i一定有prime[j+1]和prime[j]两个质因子，且prime[j]<prime[j+1]，不符合题目要求让所乘质因子是这个合数的最小质因子）。这是一种很巧妙的处理方法，但同样也很难理解，仔细思考才能理解其中道理。

 

--------------------------------------------结束分割线---------------------------------------------

蒟蒻的第一篇文章，心情有点激动，希望有所帮助。

Micro_grass原创，玄学筛由于年月已久不知道是借鉴哪位大牛的，侵删致歉。