Sieve of Eratosthenes

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

vector<bool> isPrime;
vector<int> prime, spf, phi, mobius;

void sieve(int n) {
    isPrime.assign(n + 1, true);
    spf.assign(n + 1, 0);
    phi.assign(n + 1, 1);
    mobius.assign(n + 1, 1);
    isPrime[0] = isPrime[1] = false;
    spf[1] = 1;

    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            prime.push_back(i);
            spf[i] = i;
            phi[i] = i - 1;
            mobius[i] = -1;
        }
        for (int p : prime) {
            if ((ll)i * p > n) break;
            isPrime[i * p] = false;
            spf[i * p] = p;
            if (i % p == 0) {
                phi[i * p] = phi[i] * p;
                mobius[i * p] = 0;
                break;
            }
            phi[i * p] = phi[i] * (p - 1);
            mobius[i * p] = -mobius[i];
        }
    }
}