试除法求约数的方法有哪些，AcWing 869 题目是如何实现的？

本文共计556个文字，预计阅读时间需要3分钟。

题目：给定数组求约数个数定义：给定一个正整数数组 $\{a_i\}$，对于每个正整数 $a_i$，请按照从小到大的顺序输出它的所有约数的个数。输入格式：第一行包含一个整数 $n$，表示数组的长度。接下来 $n$ 行，每行包含一个整数 $a_i$。输出格式：输出 $n$ 行，每行包含一个整数，表示对应正整数 $a_i$ 的约数个数。示例：输入：

512

1520

2430

输出：

64

68

8说明：

12的约数有：1, 2, 3, 4, 6, 12，共 6 个。

15的约数有：1, 3, 5, 15，共 4 个。

20的约数有：1, 2, 4, 5, 10, 20，共 6 个。

24的约数有：1, 2, 3, 4, 6, 8, 12, 24，共 8 个。

30的约数有：1, 2, 3, 5, 6, 10, 15, 30，共 8 个。

题目

给定 $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; }