【模板】线性筛莫比乌斯函数

#include <bits/stdc++.h>
using namespace std;
int n;
const int maxn=10010000;
int mu[maxn],prime[maxn],cnt;
bool not_prime[maxn];
inline void Get_Mu(int n) {
    mu[1]=1;
    for(int i=2;i<=n;i++) {
        if(!not_prime[i]) prime[++cnt]=i,mu[i]=-1;
        for(int j=1;prime[j]*i<=n;j++) {
            not_prime[prime[j]*i]=1;
            if(i%prime[j]==0) {
                mu[prime[j]*i]=0;
                break;
            }
            mu[prime[j]*i]=-mu[i];
        }
    }
}
int main() {
    cin>>n;
    Get_Mu(n);
    for(int i=1;i<=n;i++) cout<<mu[i]<<' ';
    return 0;
}
点赞

发表评论