素数筛：欧拉筛的更多应用

1.记录最小质因子

在欧拉筛中，每个合数被它的最小质因子筛掉。我们可以利用这个特性，在筛的过程中记录每个数的最小质因子 lp[x]（least prime factor）。

void euler_sieve(int n) {
    for (int i = 2; i <= n; i++) {
        if (!lp[i]) {
            lp[i] = i;
            primes.push_back(i);
        }
        for (int p : primes) {
            if (p > lp[i] || i * p > n) break;
            lp[i * p] = p;
        }
    }
}

2.利用最小质因子分解质因数

有了 lp[x]，我们可以快速（$O(\log x)$）分解任意 x 的质因数：

vector<pair<int, int>> factorize(int x) {
    vector<pair<int, int>> factors;
    while (x > 1) {
        int p = lp[x];
        int cnt = 0;
        while (x % p == 0) {
            x /= p;
            cnt++;
        }
        factors.push_back({p, cnt});
    }
    return factors;
}

时间复杂度：$O(\text{质因子个数})$，最坏 $O(\log n)$（因为每次至少除以 2）。