线性筛

线性筛：在(Oleft ( n ight ))时间复杂度内筛出某东西

任意积性函数都可以线性筛

下面以线性筛素数说明为什么是线性的：

void make_prime()
{
    memset(prime,true,sizeof(prime));
    prime[0]=prime[1]=false;
    for(register int i=2; i<=maxn; i++)
    {
        if( prime[i]) Prime[num++]=i;
        for(register int j=0; j<num&&i*Prime[j]<maxn; j++)
        {
            prime[i*Prime[j]] = false;
            if( !(i%Prime[j]) ) break;
        }
    }
    return ;
15 }

分析（核心）：算法的关键之处在于break语句，break是为了保证任何一个合数都是被它的最小质因子筛掉的，所以能够保证每个数都自会被访问一次，这也就保证了复杂度是线性的。

解释：根据唯一分解定理：任意一个数(n)都可以分解成：(n=p_{1}^{t_{1}}p_{2}^{t_{2}}p_{3}^{t_{3}}cdots p_{k}^{t_{k}})

所以我们要筛掉(n)的话，肯定是用 (p_{1})去筛。

如果出现了 (left ( i mod Primeleft [ j ight ] ight )==0)  则说明  (Primeleft [ j ight ]是i的质因子) ，那么此时如果我们继续用  (i*Primeleft [ j+1 ight ])  去筛某个数 (x) 的话，我们就是用  (Primeleft [ j+1 ight ])  去筛的 (x)，可是很显然  (Primeleft [ j ight ])  是(x)的一个质因子，并且  (Primeleft [ j ight ])  比  (Primeleft [ j+1 ight ])  小，所以  (Primeleft [ j+1 ight ])  不是 (x) 的最小质因子，于是break，也就保证了每个数是被它的最小质因子筛掉的。