12976.找因数

题目分析

题目要求找出一个正整数 (a) 的所有因数（即能被 (a) 整除的正整数），并将它们从小到大依次输出。数据范围 (a \le 1000)，规模很小，因此直接使用简单的枚举方法即可完成任务。

解题思路

直接从 (1) 到 (a) 枚举所有整数 (i)：

• 如果 (a \bmod i = 0)，说明 (i) 是 (a) 的因数；
• 将这些 (i) 依次输出，自然满足从小到大的顺序。

这种方法思路清晰，代码容易实现，非常适合初学者练习循环和条件判断。

算法说明

1. 读入正整数 (a)。
2. 使用 for 循环，变量 (i) 从 (1) 遍历到 (a)。
3. 每次循环中判断 (a \bmod i) 是否等于 (0)：
   • 如果是，输出 (i) 并换行；
   • 如果不是，继续下一次循环。
4. 循环结束后，所有因数已按升序输出。

时间复杂度分析

程序需要从 (1) 到 (a) 进行一轮循环，共执行 (a) 次取模和判断操作，因此时间复杂度为 (O(a))。当 (a \le 1000) 时，可以在 1ms 内轻松完成，完全满足题目限制。

参考代码及解释

下面的 C++ 代码与题目给出的参考代码在逻辑上一致，但修正了其中的笔误，并添加了必要的注释。

cpp
复制
1#include <iostream>
2using namespace std;
3
4int main() {
5    int a;
6    cin >> a;                      // 输入正整数 a
7    for (int i = 1; i <= a; ++i) { // 从 1 枚举到 a
8        if (a % i == 0) {           // 判断 i 是否是 a 的因数
9            cout << i << endl;     // 输出因数并换行
10        }
11    }
12    return 0;
13}

代码解释：

• #include <iostream>：包含输入输出流库。
• using namespace std;：使用标准命名空间，这样可以直接写 cin 和 cout 而不用加 std::。
• int main()：C++ 程序入口。
• cin >> a;：从标准输入读入正整数 (a)。
• for (int i = 1; i <= a; ++i)：循环变量 i 从 1 逐步增加到 (a)，包含了所有可能的约数取值范围。
• if (a % i == 0)：用模运算 % 检查 (a) 是否能被 i 整除，余数为 0 表示可以整除，即 i 是 a 的因数。
• cout << i << endl;：输出满足条件的因数 i，并换行。
• return 0;：程序正常退出。

拓展思考

当 (a) 很大的时候（比如 (10^9)），(O(a)) 的算法会超时，此时可以优化为只枚举 (1) 到 (\sqrt{a})：

• 如果 (i) 是 (a) 的因数，那么 (a / i) 也是因数；
• 枚举到 (\sqrt{a}) 时，同时收集两个因数，并注意去重；
• 最后对收集到的因数排序输出。

由于本题 (a \le 1000)，不需要使用这种优化，但掌握了该思路对以后解决更大规模的问题会有帮助。