试除法求约束

约数，又称因数。整数baia除以整数b(b≠0) 除得的商正好是du整数而没有余数，
我们就zhi说a能被daob整除，或b能整除a。a称为b的倍数，b称为a的约数。

时间复杂度时间复杂度O(sqrt(n));

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

using namespace std;

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

    for (int i = 1; i <= n / i; i ++ ){
        if (n % i == 0){
            //我们将i和n/i 都给放入res里，因为i和n/i的乘积为n，都是n的约数
            res.push_back(i);
            if (i != n / i) res.push_back(n / i);
        }
    }

    sort(res.begin(), res.end());//将res返回

    return res;//返回res
}
int main(){
    int n;
    scanf("%d", &n);

    while (n -- ){
        int x;
        scanf("%d", &x);

        auto res = get_divisors(x);

        for (auto t : res) printf("%d ", t);//遍历输出
        puts("");
    }

    return 0;
}