CSP-J 2020 第一轮 第 38 题：质因数分解：⑤处应填

题目

1.（质因数分解）给出正整数 $n$，请输出将 $n$ 质因数分解的结果，结果从小到大输出。

例如：输入 $n=120$，程序应该输出 2 2 2 3 5，表示：$120 = 2 \times 2 \times 2 \times 3 \times 5$。输入保证 $2\le n \le 10^9$。

提示：先从小到大枚举变量 $i$，然后用 $i$ 不停试除 $n$ 来寻找所有的质因子。

  试补全程序。

#include <cstdio>
using namespace std;
int n, i;

int main() {
  scanf("%d", &n);
  for(i = ①; ② <=n; i ++){
    ③{
      printf("%d ", i);
      n = n / i;
    }
  }
  if(④)
    printf("%d ", ⑤);
  return 0;
}

⑤处应填（ )

选项

• A. 2
• B. n/i
• C. n
• D. i

答案

C

题解

选 C. n。

不断用 i 试除并更新 n 后，如果最后剩下的 n > 1，那么它就是尚未输出的质因子，应直接输出 n。

补全程序的核心部分如下：

``cpp for (i = 2; i * i <= n; i++) { while (n % i == 0) { printf("%d ", i); n = n / i; } } if (n > 1) printf("%d ", n); ``

例如 n = 120：

• 除以 2 三次，输出 2 2 2，n 变为 15。
• 除以 3 一次，输出 3，n 变为 5。
• 接下来 i = 4，4 × 4 > 5，循环结束。
• 剩余的 n = 5 > 1，最后输出 5，所以⑤填 n。