莫比乌斯-欧拉筛

莫比乌斯-欧拉筛做法

#include<stdio.h>
#include<string.h>
long long prime[5500000];
long long vis[5500000];
long long mo[5500000];
int main()
{
    int i,j,ans=0;
    mo[1]=1;
    for(i=2; i<=1100000; i++)
    {
        if(!vis[i])
        {
            mo[i]=-1;
            prime[++prime[0]]=i;
        }
        for(j=1; j<=prime[0]&&i*prime[j]<=1100000; j++)
        {
            vis[i*prime[j]]=1; 
            if(i%prime[j]==0)   break;/*这行代码神奇地保证了每个合数只会
            被它的最小素因子筛掉，（避免一般筛法像30这样的数字 在 2* 15 ， 5 * 6 都会筛到
            筛了多次效率降低的问题）,就把复杂度降到了O(N)。*/
            mo[prime[j]*i]-=mo[i];
        }
    }
    int n;
    while(~scanf("%d",&n))
    {
        printf("%d\n",mo[n]);
    }
    return 0;
}

新手小白第一次写博客，而且代码能力也很弱，有什么不好的地方请大佬们指出来，我会加以改正