原理、思想

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

记忆要点

  1. 两个数组:一个vis[], 一个prime[]。
  2. 循环从2开始, 直到所给的上限n处(或者直接maxn)。
  3. 无论当前数是否是质数, 都要进行后续合数的处理!
  4. 筛除时要利用已有的素数。
  5. 素数规模:趋近于 <mstyle displaystyle="true" scriptlevel="0"> x l n x </mstyle> \displaystyle \frac{x}{lnx} lnxx

快乐的模板

处理出 1 e 8 1e8 1e8以内的素数用时 1 s 1s 1s左右,实测复杂度为 O ( n ) O(n) O(n)带一个小常数。

1 e 7 1e7 1e7以内则 0.1 s 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;
        }
    }
}

欧拉函数

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

1 e 7 1e7 1e7以内 0.15 s 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]];
        }
    }
}

莫比乌斯函数

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

1 e 7 1e7 1e7以内 0.15 s 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];
        }
    }
}