【模板】欧拉筛(线性筛)

优秀资料

素数

这个很好写。我们可以很好的理解埃氏筛，然后加一些优化即可得到线性筛。

inline void get_pri(int n){
    for(int i=2;i<=n;++i) not_pri[i]=0;
    not_pri[1]=1;
    for(int i=2;i<=n;++i){
        if(!not_pri[i]){
            pri[++pri[0] ]=i;
        }
        for(int j=1;j<=pri[0] and pri[j]*i<=n;++j){
            not_pri[i*pri[j] ]=1;
            if(i%pri[j]==0) break;//优化，防止重复筛同一个数
        }
    }
}

因为每个数都可以被拆分成若干个质因数，所以我们可以用枚举的数乘上素数来筛。

其实很好理解，稍微难一点的在于对于那个优化的理解。

由于我们枚举素数的时候是从小到大的，那么我们可以知道，当 i\% pri[j]==0 成立的时候, pri[j] 为 i 的最小质因子。那么接下来筛出来的东西的最小质因子是 pri[j]，这个我们交给之后的数乘上这个最小质因子来筛掉，中断循环，以此优化时间复杂度至 O(n).

欧拉函数

这个我们可以和素数一起求(因为确实要用素数)

还是同一个优化。

inline void get_Euler(int n){
    for(int i=2;i<=n;++i) not_pri[i]=0;
    not_pri[1]=1;
    phi[1]=1;
    for(int i=2;i<=n;++i){
        if(!not_pri[i]){
            pri[++pri[0] ]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=pri[0] and pri[j]*i<=n;++j){
            not_pri[i*pri[j] ]=1;
            if(i%pri[j]){
                phi[i*pri[j] ]=phi[i]*(pri[j]-1);
            }else{
                phi[i*pri[j] ]=phi[i]*pri[j];
                break;
            }
        }
    }
}

我们考率，当 i 为一个素数时,那么它显然与所有比它小的数互质，于是赋予其 i-1

当 pri[j]|i 时，我们可以得到：

\varphi(ip)=ip\Pi_{i=1}^{k}(1-\frac{1}{p_i})

由于 i 包含了 ip 的全部质因子，所以：

=p\varphi (i)

对于 pri[j]\not|i,即 gcd(pri[j],i)=1 那么欧拉函数满足积性函数的性质。 有：\varphi(ab)=\varphi(a)\varphi(b)

其他便于素数筛区别不大了。

莫比乌斯函数

照着这张图就十分简单了。

inline void get_mu(int n){
    for(int i=2;i<=n;++i){
        not_pri[i]=0;
    }
    not_pri[1]=1;
    mu[1]=1;
    for(int i=2;i<=n;++i){
        if(!not_pri[i]){
            pri[++pri[0] ]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=pri[0] and pri[j]*i<=n;++j){
            not_pri[i*pri[j] ]=1;
            if(i%pri[j]){
                mu[i*pri[j] ]=-mu[i];
            }else{
                mu[i*pri[j] ]=0;
                break;
            }
        }
    }
}

还是分情况来，对于 i 为素数，显然只有一个质因子，给上 -1 的初始值。

若 pri[j]|i,那么 i 被 pri^2[j] 整除,于是给 0 的赋值.

对于 pri[j]\not|i,那么相当于在 i 的基础上加上一个 pri[j] 的质因子，于是给 -\mu(n) 的赋值。

其实其他的积性函数大多可以用线性筛来筛，我们大多按照以上三种情况讨论即可。