素数筛法(转载+总结)

素数筛法(转载+总结)

埃氏筛

​ 埃式筛的复杂度是 O(n*loglogn)，基本上可以视为线性。

​ 它的过程是这样的：

我们把2~n的数按顺序写出来：

从前往后看，找到第一个未被划掉的数，2，这说明它是质数。然后把2的倍数（不包括2）划掉：

下一个未被划掉的数是3，它是质数，把3的倍数划掉：

接下来应该是5，但是5已经超过 16^(0.5) 了，所以遍历结束，剩下未被划掉的都是素数：

如何？是不是比一个一个判断快多了？这个过程写成代码就是：

void init_is_prime(int n)//n表示上限
{
    memset(is_prime,1,sizeof(is_prime));
    //is_prime[0]=0;is_prime[1]=0;
    for(int i=2;i<=n;i++)
    {
        if(!is_prime[i])continue;
        ans[cnt++]=i;//如果是素数的话，就加入ans中
        for(int j=i*2;j<=n;j+=i)is_prime[j]=0;
    }
}

​ 这个算法的复杂度是 O(n*loglogn) ，还是非常优秀了。但是我们可能会发现，在筛的过程中我们会重复筛到同一个数，例如12同时被2和3筛到，30同时被2、3和5筛到。所以我们引入欧拉筛，也叫线性筛，可以在 O(n)时间内完成对2~n的筛选。它的核心思想是：让每一个合数被其最小质因数筛到。

欧拉筛

我们这次除了把2~n列出来，还维护一个质数表：

还是从头到尾遍历，第一个数是2，未被划掉，把它放进质数表：

然后我们用2去乘质数表里的每个数，划掉它们：

下一个是3，加入质数表，划掉6、9：

下一个是4（注意这里划掉的数也要遍历，只是不加入质数表），先划掉8，但我们不划掉12，因为12 (12=2 x 6 = 3 x 4)应该由它的最小质因数2筛掉，而不是3。

下一个是5，加入质数表，划掉10，15：

下一个是6，划掉12，6被2整除，跳过。

……

按这样的步骤进行下去，可以筛掉所有的合数，并得到一张质数表。

详细证明见：https://zhuanlan.zhihu.com/p/100051075

void f(int n)//n表示上限
{
    memset(is_prime,1,sizeof(is_prime));
    for(int i=2;i<=n;i++)
    {
        if(is_prime[i])ans[cnt++]=i;
        for(int j=1;j<cnt&&i*ans[j]<=n;j++)
        {
            is_prime[i*ans[j]]=0;
            if(i%ans[j]==0)break;
        }
    }
}

个人总结

​ 还是多多练习欧拉筛吧，$O(n)$还是挺香的，然后还要注意数据读取的优化。

练习

洛谷P3383 【模板】线性筛素数

AC code

#include<bits/stdc++.h>
using namespace std;
bool is_prime[100000001];
long long ans[100000001];
long long read()
{
	string s;
	cin>>s;
	long long sum=0;
	for(int i=0;i<s.length();i++)
	{
		sum=sum*10+s[i]-'0';
	}
	return sum;
}
int main()
{
    long long n,q,k,cnt=1;//开longlong以防万一
    n=read();q=read();//这样读数据应该快一点
    //把函数体放在main里面省去调用函数的时间
    memset(is_prime,1,sizeof(is_prime));
    for(int i=2;i<=n;i++)
    {
        if(is_prime[i])ans[cnt++]=i;
        for(int j=1;j<cnt&&i*ans[j]<=n;j++)//注意不能越界
        {
            is_prime[i*ans[j]]=0;
            if(i%ans[j]==0)break;
        }
    }
    while(q--)
    {
        scanf("%lld",&k);
        printf("%lld\n",ans[k]);
    }
    return 0;
}