AcWing 869. 试除法求约数

题目

给定 $n$ 个正整数 $a_i$，对于每个整数 $a_i$，请你按照从小到大的顺序输出它的所有约数。

输入格式 第一行包含整数 $n$。

接下来 $n$ 行，每行包含一个整数 $a_i$。

输出格式 输出共 $n$ 行，其中第 $i$ 行输出第 $i$ 个整数 $a_i$ 的所有约数。

数据范围 $1≤n≤100,1≤a_i≤2×10^9$ 输入样例：

2
6
8

输出样例：

1 2 3 6 
1 2 4 8 

思路

与试除法判断质数类似，对于一个正整数，约数是成对出现的，我们也可以循环 $1 -- sqrt(x)$。 打印较小的那个；大的用栈（先进后出）存储，最后一起输出。

代码

#include <iostream>
#include <stack>

using namespace std;

int n;

int main()
{
    cin >> n;
    stack<int> stk;
    
    while (n -- )
    {
        int a;
        cin >> a;
        for (int i = 1; i <= a / i; i ++ )
            if (a % i == 0) 
            {
                cout << i << " ";
                if (i != a / i) stk.push(a / i);
            }
        
        while (stk.size())
        {
            cout << stk.top() << " ";
            stk.pop();
        }
        cout << endl;
    }
    
    return 0;
}