分析

• 直接用试除法求解即可。

• 另外最后需要返回的是排序后的约数，需要调用sort函数，这一步不会消耗太多时间，因为我们可以考虑1~n这n个数据总共的约数个数，考虑约数不是很容易，我们可以这样考虑：1是所有数的约数，有n个；2是所有2的倍数的约数，有$\frac{n}{2}$个；依次类推，所以1~n中一共有$n \times (1 +\frac{1}{2} + \frac{1}{3} … + \frac{1}{n})=n \times ln(n)$个约数，因此平均每个数有$ln(n)$个约数，不是很多。

• 实际上，在int范围内，约数个数最多的数据有1600个约数（程序计算出来的），$2 \times 10 ^ 9$之内约数个数最多的数据有1536个。

代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> get_divisors(int n) {
    vector<int> res;

    for (int i = 1; i <= n / i; i++)
        if (n % i == 0) {
            res.push_back(i);
            if (i != n / i) res.push_back(n / i);
        }

    sort(res.begin(), res.end());
    return res;
}

int main() {

    int n;
    cin >> n;

    while (n--) {
        int x;
        cin >> x;
        vector<int> res = get_divisors(x);
        for (auto t : res) cout << t << ' ';
        cout << endl;
    }

    return 0;
}