欧拉（Euler）筛法求素数

时间复杂度为O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void init(){ 
    phi[1]=1;
    for(int i=2;i<MAXN;i++){
        if(!vis[i]){
            phi[i]=i-1;
            pri[cnt++]=i;//cnt为素数的总数
        }
        for(int j=0;j<cnt;j++){
            if(1LL*i*pri[j]>=MAXN)break;
            vis[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;
            }
        }
    }
}

注意到筛法求素数的同时也得到了每个数的最小质因子

筛法求欧拉函数

对于一个数n，φ(n)\varphi(n)的值为1−1pi1-\frac{1}{p_i}的累乘再乘上n,其中pip_i为每一个不同的质因子

1
2
3
4
5
6
7
8
9
10
void get_phi(int n){
    for(int i=2;i<=n;i++)phi[i]=0;
    phi[1]=1;
    for(int i=2;i<=n;i++)
        if(!phi[i])
            for(int j=i;j<=n;j+=i){
                if(!phi[j])phi[j]=j;
                phi[j]=phi[j]/i*(i-1);
            }
}

筛法求莫比乌斯函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void get_mu(){
    mu[1]=1;
    for(int i=2;i<MAXN;i++){
        if(!v[i])mu[i]=-1,p[tot++]=i;
        for(int j=0;j<tot&&i<=MAXN/p[j];j++){
            v[i*p[j]]=1;
            if(i%p[j]==0){
                mu[i*[j]]=0;
                break;
            }
            mu[i*p[j]]=-mu[i];
        }
    }
}

筛法求约数个数

d[i]表示i的约数个数，num[i]表示i的最小质因子出现次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void get_d(){
    d[1]=1;
    for(int i=2;i<MAXN;i++){
        if(!v[i])v[i]=1,p[tot++]=i,d[i]=2,num[i]=1;
        for(int j=0;j<tot&&i<=MAXN/p[j];j++){
            v[p[j]*i]=1;
            if(i%p[j]==0){
                num[i*p[j]]=num[i]+1;
                d[i*p[j]]=d[i]/(num[i]+1)*(num[i*p[j]]+1);
                break;
            }
            else {
                num[i*p[j]]=1;
                d[i*p[j]]=d[i]*2;
            }
        }
    }
}

筛法求约数和

f[i]表示i的约数和， g[i]表示i的最小质因子pp的p0+p1+⋯+pnp^0+p^1+\cdots+p^n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void get_sum(){
    g[1]=f[1]=1;
    for(int i=2;i<MAXN;i++){
        if(!v[i])v[i]=1,p[tot++]=i,g[i]=i+1,f[i]=i+1;
        for(int j=0;j<tot&&i<=MAXN/p[j];j++){
            v[p[j]*i]=1;
            if(i%p[j]==0){
                g[i*p[j]]=g[i]*p[j]+1;
                f[i*p[j]]=f[i]/g[i]*g[i*p[j]];
                break;
            }
            else {
                f[i*p[j]]=f[i]*f[p[j]];
                g[i*p[j]]=1+p[j];
            }
        }
    }
}