math/mobius_all.cpp

• View this file on GitHub
• Last update: 2020-04-26 17:42:59+09:00

Code

vector<int> mobius_all(int M){
    vector<int> mobius(M), isprime(M);
    for (int i = 0; i < M; ++i) {
        mobius[i] = isprime[i] = 1;
    }
    for (int i = 2; i < M; ++i) {
        if(isprime[i]){
            for (int j = i; j < M; j += i) {
                mobius[j] = -mobius[j];
                isprime[j] = 0;
            }
            isprime[i] = 1;
            ll x = (ll)i*i;
            if(x <= M){
                for (int j = x; j < M; j += x) {
                    mobius[j] = 0;
                }
            }
        }
    }
    return mobius;
}

#line 1 "math/mobius_all.cpp"
vector<int> mobius_all(int M){
    vector<int> mobius(M), isprime(M);
    for (int i = 0; i < M; ++i) {
        mobius[i] = isprime[i] = 1;
    }
    for (int i = 2; i < M; ++i) {
        if(isprime[i]){
            for (int j = i; j < M; j += i) {
                mobius[j] = -mobius[j];
                isprime[j] = 0;
            }
            isprime[i] = 1;
            ll x = (ll)i*i;
            if(x <= M){
                for (int j = x; j < M; j += x) {
                    mobius[j] = 0;
                }
            }
        }
    }
    return mobius;
}

Back to top page