c++ 有N(n<=1e3)个数字ai(ai<=4e6)，找到每个ai的第二大因数，O(N)

好的，这里提供一个时间复杂度为 $O(N)$ 的 C++ 实现，解决了找到每个 $a_i$ 的第二大因数的问题。

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

const int N = 4e6 + 5;

int prime[N], min_prime[N], cnt;
bool is_prime[N];
int max_factor[N], sec_max_factor[N];

void init(int n) {
    memset(is_prime, true, sizeof(is_prime));
    is_prime[0] = is_prime[1] = false;
    cnt = 0;
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            prime[cnt++] = i;
            min_prime[i] = i;
        }
        for (int j = 0; j < cnt && prime[j] * i <= n; j++) {
            is_prime[i * prime[j]] = false;
            min_prime[i * prime[j]] = prime[j];
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
}

void prework(int n) {
    for (int i = 1; i <= n; i++) {
        int x = i;
        while (x > 1) {
            int p = min_prime[x];
            int cnt = 0;
            while (x % p == 0) {
                x /= p;
                cnt++;
            }
            if (cnt >= max_factor[i]) {
                sec_max_factor[i] = max_factor[i];
                max_factor[i] = cnt;
            } else if (cnt > sec_max_factor[i]) {
                sec_max_factor[i] = cnt;
            }
        }
    }
}

int main() {
    init(N - 1);
    prework(N - 1);
    int n;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        if (max_factor[x] <= 1) {
            cout << -1 << endl;
        } else {
            cout << sec_max_factor[x] << endl;
        }
    }
    return 0;
}

首先，我们使用线性筛法预处理出 $[1, 4 \times 10^6]$ 中的所有质数和最小质因子，然后对于每个 $a_i$，我们将其分解质因数，并统计质因子的个数。在统计质因子个数的过程中，我们同时维护每个数的最大因子个数和次大因子个数，最后输出次大因子个数即可。

这个算法的时间复杂度为 $O(N)$，可以在 $1 \text{s}$ 内解决 $N \leq 10^3$ 的数据规模。