筛素数算法（一）——线性筛素数算法

时间复杂度：O(nlogn)

先上代码（代码后面有解析）：

#include<bits/stdc++.h>
using namespace std;
int n;
map<int,int> Is_Prime;//保存每一个数是否为质数
vector<int> Prime;//保存全部质数
int main()
{
	scanf("%d",&n);//筛选2~n内的质数
	for(int i=2;i<=n;i++) Is_Prime[i]=1;//先默认全部都是质数
	for(int i=2;i<=n;i++)
	{
		if(Is_Prime[i]) Prime.push_back(i);//如果这个数是质数，就将其保存下来
		for(int j=0;j<Prime.size();j++)//将这个数与已有的质数进行操作
		{
			Is_Prime[i*Prime[j]]=0;//将这个数与该质数的积标记为非质数
			if(!(i%Prime[j])) break;//如果当前数是该质数的倍数，就退出循环（这个在后面会进行解释）
		}
	}
    //以下为输出部分
	printf("%d\n",Prime.size());
	for(int i=0;i<Prime.size();i++) printf("%d ",Prime[i]);
	return 0;
}
           

下面是对"if(!(i%Prime[j])) break"这个语句的解释：

对于2~n之间的一个整数i,有两种可能性：

一：它是质数。则此时Prime[j]必为i（一个质数只能被1和本身整除，而Prime[j]不可能为1，故Prime[j]为i），而i是刚保存下来的，必然在最末尾，即i后面没有其他可操作的数了，于是退出循环

二：它是合数。则可得i=Prime[j]*x（x为2~i之间的一个整数），此时又有两种可能性：

  1：x是质数。则x>=Prime[j]（若x<Prime[j]，则在对Prime[j]进行操作前就会对x进行操作并退出循环），那么i与Prime[j]之后的任意一个数t的积i*t都可以表示为Prime[j]*x*t，而x*t是一个合数，所以在轮到对x*t和Prime[j]进行操作时时就可以得到i*t，故不需要继续操作了，可以退出循环

  2：x是合数。则x可以分解为a*b的形式（其中a是所能取值的数中的最小质数），那么i=a*b*Prime[j]。对于a和Prime[j]的大小关系，有两种可能性：

    ①：a<Prime[j]。显然不可能（否则在对Prime[j]进行操作前就会对a进行操作并退出循环）

    ②：a>=Prime[j]。∵a>=Prime[j],∴b*Prime[j]<=x，那么i应在对x进行操作就已经在对b*Prime[j]进行操作的时候的时候被判定为非质数,自然无需再判一遍

证毕。

注：如果您通过此文学会了线性筛，请您点个赞再离开。当然，也欢迎在讨论区指出此文的不足处，作者会及时对此文加以修正

版权声明：转载请注明地址