AcWing - 試除法求約數(試除法)

題目連結:https://www.acwing.com/problem/content/description/871/

時/空限制：1s / 64MB

題目描述

給定n個正整數ai，對于每個整數ai,請你按照從小到大的順序輸出它的所有約數。

輸入格式

第一行包含整數n。

接下來n行，每行包含一個整數ai。

輸出格式

輸出共n行，其中第 i 行輸出第 i 個整數ai的所有約數。

資料範圍

1≤n≤100,

2≤ai≤2∗10^9

輸入樣例

2

6

8

輸出樣例

解題思路

/* 
 * @Author: lzyws739307453 
 * @Language: C++ 
 */
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
int pre[MAXN];
int get_divisors(int n) {
    int cnt = 0;
    for (int i = 1; i <= n / i; i++) {
        if (!(n % i)) {
            pre[cnt++] = i;
            if (i != n / i)
                pre[cnt++] = n / i;
        }
    }
    sort(pre, pre + cnt);
    return cnt;
}
int main() {
    int t, n;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        int cnt = get_divisors(n);
        for (int i = 0; i < cnt; i++)
            printf("%d ", pre[i]);
        printf("\n");
    }
    return 0;
}