我们已经见证了线性筛有多么强大，它强大到 4·10⁸ 内的所有素数可以在 1.6s 内求出， 而普通筛法只需要+1s 。所以这么好的一个算法，可以为你续一秒，何乐而不用呢?

用法 1：筛素数

void get_prime()
{    
    int pnum = 0;
    for(int i = 2; i < MAX; i++)
    {    
        if(!vis[i]) p[++pnum] = i; 
        for(int j = 1; j <= pnum && i * p[j] < MX; j++) 
        {    
            vis[i * p[j]] = true; 
            if(i % p[j] == 0) 
                break; 
        } 
    } 
}

---

用法 2：筛欧拉函数

欧拉函数是数论中重要的函数，phi(x) 表示小于等于 x 的正整数中有几个与其互质。
以下是它的一些性质: (出现的 p,q 都是质数)


(0): phi(ab)=phi(a)phi(b) (a,b 互质)

证明：根据唯一 分解定理，a,b 均可以分解为若干个互不相同的质数的幂次之积，那么 ab 就是 a,b 的分解之积，因为 a,b 没有公约数，所以 ab 的约数个数就是 (a 的 b 的)，所以 phi(ab) 同样满足积性。

(1): phi(p)=p-1

证明：显然。

(2): phi(ip)=pphi(i) (i%p=0)

证明：首先证明两个引理：a. 如果 i%p=0, 那么 (i+p)%p=0。b. 如果 i%p!=0, 那么 (i+p)%p!=0。这两个是显然的。所以在 [1,i] 这个区间中与 i 互质的数，同时加上 i, 仍旧与 i+i 互质，不互质的依旧不互质。所以以此类推，[1,pi] 这个区间中有 pphi(i) 个数与 p*i 互质。证明完毕。(也许会有漏洞不过结论是对的)

(3): phi(ip)=phi(i)(p-1) (i%p!=0)

证明：i%p 不为 0 且 p 为质数, 所以 i 与 p 互质, 那么根据欧拉函数的积性 phi(i * p)=phi(i) * phi(p) 其中 phi(p)=p-1 即第一条性质
由上面的４个结论，我们就可以将欧拉函数的求解插入到线性筛中，在筛素数的过程中顺便求出 [1,n] 区间中的每一个欧拉函数值。

void solve(int n)
{
    phi[1]=1;
    for(int i=2;i<=n;i++)
  {
        if(!vis)
        {
            p[++pnum]=i;
            phi[i]=i-1;                                                          //p 为素数的结论
        }
        for(int j=1,k;j<=pnum&&(k=i*p[j])<=n;j++)
        {
            vis[k]=1;
            if(i%pris[j]==0)
            {
                phi[k]=phi[i]*p[j];                                        //如果 i%p==0 的结论
                break;
            }
            phi[k]=phi[i]*(p[j]-1);                                      //如果 i%p!=0 的结论
        }
    }
}

---

用法３：筛莫比乌斯函数

莫比乌斯函数是莫比乌斯反演中的必须函数，其中 miu(x) 表示 x 的莫比乌斯函数值。
一下是它的一些性质，证明就不给出了，因为这个函数是直接定义的，而不是像欧拉函数一样通过定义求出的。
官方对μ(x) 的定义是这样的:
(0)：μ是一个关于整数的函数
(1)：μ[x] = 1 当且仅当 x 能够分解成偶数个不同质数的乘积（其中 1 不能被分解，所以 1 的分解出的质数个数是 0，所以μ[1]=1）
(2)：μ[x] = -1 当且仅当 x 能够分解成奇数个不同质数的乘积
(3)：μ[x] = 0 除开 (2),(3) 的其他情况
我们也可以得到这个函数的线性筛法：

void init()
{
    miu[1]=1;                                             //根据定义０
    pnum=0;
    for(ll i=2;i<=MX;i++)
    {
        if(!vis[i])p[++pnum]=i,miu[i]=-1;   //根据定义２
        for(ll j=1;j<=pnum;j++)
        {
            if(i*p[j]>=MX)break;
            vis[i*p[j]]=1;
            if(i%p[j]==0)
            {
                miu[i*p[j]]=0;                                //根据定义３
                break;
            }
            else miu[i*p[j]]=-miu[i];                //根据定义１，２
        }
    }
}

用法 4：筛最小质因子

我们给出一个结论：线性筛中每一个数字都被其最小质因子筛去。因此：

void init()
{
    miu[1]=1;
    for(int i=2;i<MX;i++)
    {
        if(!vis[i])prm[++pnum]=i,,myz[i]=i;
        for(int j=1;j<=pnum;j++)
        {
            if(i*prm[j]>=MX)break;
            myz[i*prm[j]]=prm[j];
            vis[i*prm[j]]=1;
            if(i%prm[j]==0)break;
        }
    }
}

这就是我们线性筛法的主要应用~