linear eratosthenes sieve

vector<int> lp(n + 1, 0), pr;
for (int i = 2; i <= n; i++) {
    if (lp[i] == 0) {
        lp[i] = i;
        pr.pb(i);
    }

    for (int p : pr) {
        if (p * i > n || p > lp[i]) break;
        lp[p * i] = p;
    }
}