莫比乌斯函数线性筛

#include"iostream"
#include"vector"
#include"string.h"
using namespace std;
const int maxn=1e5;
bool PP[maxn+10];
vector<int> prime;
int mu[maxn+10];
//int Moblus(int n)
//{
// if(n==1)return 1;
// int cnt=0,u=1;
// for(int i=2;i*i<=n;i++)
// {
// cnt=0;
// if(n%i==0)
// {
// u=-u;
// }
// while(n%i==0)
// {
// n/=i;
// cnt++;
// }
// if(cnt>=2)return 0;
// }
// if(n>1)u=-u;
// return u;
//}
void Moblus()
{
    mu[1]=1;
    memset(PP,1,sizeof(PP));
    for(int i=2;i<=maxn;i++)
    {
        if(PP[i])
        {
            prime.push_back(i);
            mu[i]=-1;
        }
        for(int j=0;j<prime.size()&&i*prime[j]<=maxn;j++)
        {
            PP[i*prime[j]]=0;
            if(i%prime[j]==0)
            {
                mu[i*prime[j]]=0;
                break;
            }
            else mu[i*prime[j]]=-mu[i];
        }
    }
}
int main()
{
    Moblus();
    for(int i=1;i<=maxn;i++)cout<<mu[i]<<" ";
}