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

好的，我可以给你两个算法实现，一个是 $O(nlogn)$ 的，另一个是 $O(n)$ 的。

【算法一】$O(nlogn)$

1. 对于每个数字ai，找到它的所有因数。可以使用暴力枚举的方法，从1到sqrt(ai)遍历所有的数，判断是否为ai的因数，将其加入因数数组中。

2. 将因数数组排序。

3. 找到第二大的因数。因为数组已经按照从小到大的顺序排序，所以第二大的因数就是数组中倒数第二个元素。

以下是使用 Python 代码实现上述算法的示例：

import math

def find_second_largest_factor(n):
    factors = []
    for i in range(1, int(math.sqrt(n))+1):
        if n % i == 0:
            factors.append(i)
            if n // i != i:
                factors.append(n // i)
    factors.sort()
    if len(factors) < 2:
        return -1
    return factors[-2]

# 示例
n = 100
for i in range(1, n+1):
    print(i, find_second_largest_factor(i))

在上述代码中，我们使用了一个数组「factors」来存储n的所有因数，并对其进行排序。最后，我们返回数组中倒数第二个元素作为第二大因数。

【算法二】$O(n)$

1. 对于每个数字ai，找到它的最大因数和次大因数。可以使用一个桶来存储每个数的因数，同时维护一个数组，存储每个数的最大因数和次大因数。

2. 遍历桶中的每个数，找到该数的最大因数和次大因数。

以下是使用 Python 代码实现上述算法的示例：

def find_second_largest_factor(n):
    factors = [0] * (n+1)
    max_factors = [-1] * (n+1)
    sec_max_factors = [-1] * (n+1)

    for i in range(1, n+1):
        for j in range(i, n+1, i):
            factors[j] += 1

        if factors[i] >= max_factors[i]:
            sec_max_factors[i] = max_factors[i]
            max_factors[i] = factors[i]
        elif factors[i] >= sec_max_factors[i]:
            sec_max_factors[i] = factors[i]

    if sec_max_factors[n] == -1:
        return -1
    return sec_max_factors[n]

# 示例
n = 100
for i in range(1, n+1):
    print(i, find_second_largest_factor(i))

在上述代码中，我们使用了一个桶来存储每个数的因数个数，同时维护了一个数组，存储每个数的最大因数和次大因数。最后，我们返回次大因数即可。

这两个算法的时间复杂度分别为 $O(nlogn)$ 和 $O(n)$，你可以根据你的具体情况选择其中一个算法来解决问题。