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

题目

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. n>1
• B. n<=1
• C. i<n/i
• D. i+i<=n

答案

A

题解

选 A：n > 1。

试除时，每找到一个质因子 i，就输出它，并将 n 除以 i，直到不能整除。

循环通常在 i * i > n 时结束。此时：

• 若 n == 1，说明所有质因子都已经输出。
• 若 n > 1，剩下的 n 一定是质数，需要再输出它。否则，它必然有一个不超过 $\sqrt n$ 的质因子，早就被试除掉了。

因此最后应写： ``cpp if (n > 1) printf("%d ", n); ``

例如 120 依次除去 2、2、2、3 后，剩下 n = 5，就靠这个判断输出最后的 5。