1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
|
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; }
|
近期评论