求x的所有质因子，时间复杂度$O(\sqrt x)$；

如果求n个数的质因子（每个数不超过x），时间复杂度$O(n \sqrt x)$

vector<int> fac;
for (int j = 2; j * j <= x; j++) {
    if (x % j)
        continue;
    fac.push_back(j);
    while (x % j == 0)
        x /= j;
}
if (x!=1) fac.push_back(x);

使用线性筛，预处理出不超过x的每个数的最小质因子。

求x的所有质因子，时间复杂度$O(x + log x)$；

如果求n个数的质因子（每个数不超过x），时间复杂度$O(x + nlogx)$

vector<int> p;
int lpf[N]; 

void sieve() {
    lpf[1] = 1;
    for (int i = 2; i < N; i++) {
        if (lpf[i] == 0) {
            lpf[i] = i;
            p.push_back(i);
        }
        for (int j = 0; p[j] * i < N; j++) {
            lpf[p[j] * i] = p[j];
            if (i % p[j] == 0) {
                break;
            }
        }
    }
    // for (int i : p) {
    //     cout << i << "\\n";
    // }
    // for (int i = 1; i < N; i++) {
    //     cout << i << " " << lpf[i] << "\\n";
    // }
}

vector<int> fac;
while (lpf[x] != 1) {
    if (fac.empty() || fac.back() != lpf[x])
        fac.push_back(lpf[x]);
    x /= lpf[x];
}