线性筛是一个很基础的算法，但是我一直没学。直到一次考试，因为O（n√n）会超时，用了表筛，结果被卡了代码长度，于是开始学习欧拉筛。
算法思路：
对于每一个数（无论质数合数）x，筛掉所有小于x最小质因子的质数乘以x的数。比如对于77,它分解质因数是7*11，那么筛掉所有小于7的质数*77，筛掉2*77、3*77、5*77。
好吧，是不是听起来太简单了。。。。没事，重点在证明。
算法证明：
首先我们要明确证明思路。如果要证明它是对的，只要保证两点：没用重复筛、没有漏筛
1、没有重复筛。
我们假设一个合数分解成p1*p2*p3，并且保证p1p1,所以这样是筛不到的。唯一会筛的是第一种：p1和p2*p3。
2、没有漏筛。
还是假设把这个合数分解质因数a*b*c，保证a
证明没看懂的直接看代码吧。。挺好背的。
#include
#include
#include
#include
#include
#define in(a) a=read()
#define REP(i,k,n) for(int i=k;i<=n;i++)
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar())
if(ch=='-')
f=-1;
for(;isdigit(ch);ch=getchar())
x=x*10+ch-'0';
return x*f;
}
int prime[1000010],book[1000010];
int n,ind;
int main(){//计算1~n的素数
in(n);
REP(i,2,n){
if(!book[i]) prime[++ind]=i;//如果没有筛过，记录素数
REP(j,1,ind){//其中记录数组里的素数保证严格递增
if(i*prime[j]>n) break;//保证小于n，要不然没有意义
book[i*prime[j]]=1;//筛去这个合数
if(!i%prime[j]) break;//如果>=这个数的最小质因子，那就结束
}
}
REP(i,1,ind) printf("%d ",prime[i]);//输出
}