模板-线性筛莫比乌斯函数

using namespace std;
int n;
const int maxn=10010000;
int mu[maxn],prime[maxn],cnt;
bool not_prime[maxn];
inline void (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;
}