顾名思义，素数筛就是用来筛素数的。。。
1.埃氏筛 O(nloglogn)
对于一般（不毒瘤）的素数题，埃氏筛就够了
原理：任何合数都有小于自身的质因数
内容：对于每一个素数将它的 2*i～[x/i]*i全部标记为1，使得所有的合数全被标记
不足：合数会被标记素因数次，不够高效
void prime(int x)
{
for(int i=2;i<=x;i++)
{
if(!vis[i])
{
p[++cnt]=i;
for(int j=1;j<=i&&j*i<=x;j++) vis[i*j]=1;
}
2.线性筛/欧拉筛 O(n)
线性比埃氏快了那么一丢丢，一般来说可以忽略不计。。。loglogn对于一般的筛法就是个位数。。。
理念：对于任意数，筛去它的素数倍，直到遇到自身的质因数
void pri(int x)
{
vis[1]=1;
for(int i=2;i<=n;i++)
{
if(!vis[i]) prime[++num]=i;
for(int j=1;j<=num;j++)
{
if(prime[j]*i>n) break;
vis[prime[j]*i]=1；
}
}
}
3.区间筛
总有些毒瘤出题人不满足于以上两种算法，用一些超大数据折腾蒟蒻(me)们
于是，区间筛横空出世
区间筛针对一定区间[l,r],统计区间中素数个数
理念：对于<=r的数，其质因数<=√r，因此对于[l,r]开一个vis[],然后用2~√r筛一遍，剩下的就是质数了，前提：r-l < = 1000000
从根本上说，就是在大区间上（稍稍优化过的）暴力求解
素数筛( 埃氏筛、线性筛、区间筛）
原文：https://www.cnblogs.com/adaxyy/p/14108530.html
