定义：
线性筛是在O(nlog(log(n)))的Eratosthenes筛法基础上改进得到的一种算法，可以O(n)求得1~n中的所有素数，因此经常在一些与素数有关的问题中用于预处理。对线性筛进行扩展之后，又可以计算出几乎所有的积性函数。
PS：素数密度据一位老师所说是O(n/ln(n))的。
原理：
线性筛的基础思想与Eratosthenes筛法相同，不再赘述。Eratosthenes筛法在运行过程中，含有多个质因子的数会被重复筛掉。例：30=2*3*5，则它会被2，3，5都筛一遍，而这显然是没有必要的。线性筛正是从这个地方着手改进得来。
线性筛的核心思想就是在筛的过程中，每个合数都只被它的最小质因子筛去。这样就能保证每个合数都只被筛一次，复杂度为O(n)。
下面是线性筛的代码：
void prime()
{
int i,j;
p[1]=1;
for(i=2;i<=n;i++)
{
if(!p[i]){b[++tot]=i;}
for(j=1;j<=tot&&i*b[j]<=n;j++)
{
p[i*b[j]]=1;
if(i%b[j]==0){break;}
}
}
}
可以发现，线性筛与Eratosthenes筛的区别仅仅是多了一条语句。下面来证明这条语句能使每个合数都只被它的最小质因子筛去。
证明：由p[i*b[j]]=1;又由每个合数都只被它的最小质因子筛去可知，b[j]是i*b[j]的最小质因子。又因为b数组是单调增的，如果i中有b[j]这个质因子，则b[j+1],b[j+2]......一定都不是i*b[j+1],i*b[j+2],......的最小质因子，因此在i基础上的筛没有必要进行下去，直接跳出循环。
至此，我们便实现了O(n)筛出1~n的所有素数。
例题：
Luogu P3383 【模板】线性筛素数 题目链接
题解：
线性筛裸题，直接使用即可。这道题用Eratosthenes筛也可以过，但速度差异明显。
扩展：积性函数的计算
定义：
对于一个数论函数f(x)，gcd(a,b)=1,如果有f(a*b)=f(a)*f(b),则称f(x)具有积性。
常见的积性函数：欧拉函数φ，莫比乌斯函数μ，约数幂次和dk. ，gcd(n,k)（k为给定整数）
原理：
在原有线性筛中额外求一个数组h，h[i]表示i的最小质因子的幂次。即：x=p1a1+p2a2+......，（ai!=0,p1<p2<......）则h[x]=p1a1。
在线性筛结束之后，从1~n线性递推，由gcd(h[i],i/h[i])=1，f(i)=f(h[i])*f(i/h[i])。
当i=pk 时需要特殊处理，一般从该积性函数的定义就可以直接计算。例：φ(pk )=pk -pk-1 。
至此，我们便实现了线性筛的扩展。
代码（线性筛求φ）：
#define LL long long
void prime()
{
LL i,j,k;
p[1]=1;phi[1]=1;
for(i=2;i<maxn;i++)
{
if(!p[i]){b[++tot]=i;h[i]=i;}
for(j=1;j<=tot&&i*b[j]<maxn;j++)
{
p[i*b[j]]=1;h[i*b[j]]=b[j];
if(i%b[j]==0){h[i*b[j]]=h[i]*b[j];break;}
}
}
for(i=1;i<=tot;i++){for(j=b[i];j<maxn;j*=b[i]){phi[j]=j-j/b[i];}}
for(i=2;i<maxn;i++){phi[i]=phi[h[i]]*phi[i/h[i]];}
}