Линейное решето Эйлера: как за O(n) посчитать наименьший простой делитель каждого числа?

Идея линейного решета: каждое составное число x мы вычёркиваем ровно один раз — через представление x = lp[x] · m, где lp[x] — наименьший простой делитель. Это и даёт O(n): нет повторных вычёркиваний.

const int N = 1e7 + 5;
int lp[N];          // наименьший простой делитель i
vector<int> primes; // все простые до N

void linear_sieve(int n) {
    for (int i = 2; i <= n; i++) {
        if (lp[i] == 0) {        // i простое
            lp[i] = i;
            primes.push_back(i);
        }
        for (int p : primes) {
            if (p > lp[i] || (long long)i * p > n) break;
            lp[i * p] = p;
        }
    }
}

Ключевой момент — условие if (p > lp[i]) break;. Мы домножаем i только на простые p ≤ lp[i]. Тогда для числа i*p его наименьший простой делитель — это именно p (потому что p ≤ lp[i]), и оно будет помечено именно из пары (i, p), и больше никогда. Каждое составное число встречается ровно в одной такой паре → каждое вычёркивание уникально → O(n) по времени, O(n) по памяти.

Факторизация через lp потом тривиальна и работает за O(log x):

vector<int> factorize(int x) {
    vector<int> f;
    while (x > 1) { f.push_back(lp[x]); x /= lp[x]; }
    return f;
}