CSP-J 2022 第一轮 第 38 题：枚举因数：④处应填

题目

（枚举因数）从小到大打印正整数 $n$ 的所有正因数。

试补全枚举程序。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;

    vector<int> fac;
    fac.reserve((int)ceil(sqrt(n)));

    int i;
    for (i = 1; i * i < n; ++i){
        if (①){
            fac.push_back(i);
        }
    }

    for (int k = 0; k < fac.size(); ++k){
        cout << ② << "";
    }
    if (③) {
        cout << ④ << "";
    }
    for (int k = fac.size() - 1; k >= 0; --k){
        cout << ⑤ << "";
    }
}

④处应填（ ）

选项

• A. n-i
• B. n-i+1
• C. i-1
• D. i

答案

D

题解

选 D. i。

因数是成对出现的：若 i 是 n 的因数，那么 n / i 也是。程序先输出小于 $\sqrt n$ 的因数，再倒序遍历 fac，输出对应的大因数。

注意循环条件是 i * i < n，因此循环结束时：

• 若 i * i == n，说明 n 是完全平方数，需要单独输出一次因数 i。
• 否则，不需要补充输出。

所以③应填 i * i == n，④应填 i。

例如 n = 36，fac 中保存 1、2、3、4，循环结束时 i = 6。中间输出 6，最后输出 9、12、18、36，就得到了从小到大的所有正因数。