Möbius Function - YessineJallouli/Competitive-Programming GitHub Wiki

Generate Möbius Function :

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e5+7;
bool prime[N];
int mobius[N];

int main() {
    for (int i = 2; i < N; i++) {
        mobius[i] = -1;
        prime[i] = true;
    }
    for (int i = 2; i < N; i++) {
        if (prime[i]) {
            mobius[i] = 1;
            for (int j = 2*i; j < N; j+= i) {
                prime[j] = false;
                mobius[j] = j%(i*i) == 0 ? 0 : -mobius[j];
            }
        }
    }
}

Resources :
https://www.youtube.com/watch?v=j4SNmckTZYI