线性筛总结

线性筛

总体思想：筛某个合数时，总是这个数的最小质因数筛除它。

划重点 ：因数个数 $d\left(n\right)$d(n)、因数和 $s\left(n\right)$s(n)、欧拉函数 $phi\left(n\right)$phi(n)、莫比乌斯函数 $mu\left(n\right)$mu(n)等均为 $n$n的积性函数，能很好的利用“最小质因数”筛法性质。

一、筛质数

处理出 $1e8$1e8以内的素数用时 $1s$1s左右，实测复杂度为 $O\left(n\right)$O(n)带一个小常数。

$1e7$1e7以内则 $0.1s$0.1s左右。

const int maxn = 1e7+7;
const int maxp = 7e5+7;

bool vis[maxn];
int prime[maxp], tot;

void getPrime() {
    for(int i=2; i<maxn; ++i) {
        if(!vis[i]) prime[++tot]=i;
        for(int j=1; j<=tot&&i*prime[j]<maxn; ++j) {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
}

二、因数个数

d数组：d函数
num数组：最小质因数个数

const int maxn = 1e6+7;

int d[maxn], num[maxn], vis[maxn], p[maxn], tot;

void getDiv() {
    d[1]=1;
    for(int i=2; i<maxn; ++i) {
        if(!vis[i]) p[++tot]=i, d[i]=2, num[i]=1;
        for(int j=1; j<=tot&&i*p[j]<maxn; ++j) {
            int k=i*p[j]; vis[k]=1;
            if(i%p[j]==0) {
                num[k]=num[i]+1;
                d[k]=d[i]/num[k]*(num[k]+1);
                break;
            }
            num[k]=1;
            d[k]=d[i]*2;
        }
    }
}

三、因数和

s数组：s函数（ $1e6$1e6的s在 $1e6$1e6左右，用 $int$int即可）
g数组：最小质因数对应的： ${\displaystyle \frac{p^{e+1}-1}{p-1}=1+p+p^2+\cdots +p^e=1+p\ast (1+p+\cdots +p^{e-1})}$p−1pe+1−1​=1+p+p2+⋯+pe=1+p∗(1+p+⋯+pe−1)

const int maxn = 1e6+7;

int s[maxn], g[maxn], vis[maxn], p[maxn], tot;

void getSum() {
    s[1]=g[1]=1;
    for(int i=2; i<maxn; ++i) {
        if(!vis[i]) p[++tot]=i, s[i]=i+1, g[i]=i+1;
        for(int j=1; j<=tot&&i*p[j]<maxn; ++j) {
            int k=i*p[j]; vis[k]=1;
            if(i%p[j]==0) {
                g[k]=g[i]*p[j]+1;
                s[k]=s[i]/g[i]*g[k];
                break;
            }
            g[k]=p[j]+1;
            s[k]=s[i]*g[k];
        }
    }
}

四、欧拉函数

phi数组：欧拉函数

const int maxn = 1e7+7;
const int maxp = 7e5+7;

int prime[maxp], phi[maxn], tot;
bool vis[maxn];

void getPhi() {
    phi[1]=1;
    for(int i=2; i<maxn; ++i) {
        if(!vis[i]) prime[++tot]=i, phi[i]=i-1;
        for(int j=1; j<=tot&&i*prime[j]<maxn; ++j) {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j]; break; }
            phi[i*prime[j]]=phi[i]*phi[prime[j]];
        }
    }
}

五、莫比乌斯函数

mu数组：莫比乌斯函数

const int maxn = 1e7+7;
const int maxp = 7e5+7;

int prime[maxp], mu[maxn], tot;
bool vis[maxn];

void getMu() {
    mu[1]=1;
    for(int i=2; i<maxn; ++i) {
        if(!vis[i]) prime[++tot]=i, mu[i]=-1;
        for(int j=1; j<=tot&&i*prime[j]<maxn; ++j) {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0) { mu[i*prime[j]]=0; break; }
            mu[i*prime[j]]=-mu[i];
        }
    }
}