欧拉筛+欧拉函数+莫比乌斯函数

原理、思想

1. 通过已知素数及当前自然数筛掉后面的合数。
2. 同时让每一个合数只被筛去一次，摒弃重复的筛除操作。

记忆要点

1. 两个数组：一个vis[]， 一个prime[]。
2. 循环从2开始， 直到所给的上限n处（或者直接maxn）。
3. 无论当前数是否是质数， 都要进行后续合数的处理！
4. 筛除时要利用已有的素数。
5. 素数规模：趋近于 ${\displaystyle \frac{x}{lnx}}$lnxx​

快乐的模板

处理出 $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;
        }
    }
}

欧拉函数

利用积性函数性质，上面的欧拉筛稍微加点东西就好了。

$1e7$1e7以内 $0.15s$0.15s左右

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]];
        }
    }
}

莫比乌斯函数

同利用积性函数性质，上面的欧拉筛稍微加点东西就好了。

$1e7$1e7以内 $0.15s$0.15s左右

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];
        }
    }
}