C++ 线性筛法

for(int i=2;i<=mx;++i){
    if(!inp[i])prm[++cnt]=i;
    for(int j=1;j<=cnt&&(t=prm[j]*i)<=mx;++j){
        inp[t]=1;
        if(!(i%prm[j]))break;
    }
}

保证线性的关键在那个if语句,现在解释一下.
看得出来,使得if语句执行的prm[j]一定是i的最小质因子.
那么设.
若我们继续枚举,那么我们会筛掉,即.此处,那么.
换一种写法,即.发现.
那么我们可以在枚举更大的i的时候筛掉t.好吧那我们就不必在此继续了,break.
那么每个数都只会被它最大的因子×最小质因子筛掉,因此只会被筛掉一次.所以线性由此而来.