欧拉筛线性筛素数+莫比乌斯的mu[]

2024-09-02 21:10:22

https://blog.csdn.net/qq_39763472/article/details/82428602

模板来自https://blog.csdn.net/Avalon_cc/article/details/81663214

bool isP[N];

int P[N], ind;

void Euler() {

    mem(isP,);

    mu[]=; ind=;

    for(int i=;i<N;i++) {

        if(isP[i]) P[ind++]=i, mu[i]=-;

        for(int j=;j<ind;j++) {

            if(i*P[j]>N) break;

            isP[i*P[j]]=;

            if(i%P[j]==) {

                mu[i*P[j]]=; break;

            } else mu[i*P[j]]=-mu[i];

        }

    }

} // 欧拉筛

最新文章

热门文章