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

题目

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/i
• B. n/(i*i)
• C. i*i
• D. i*i*i

答案

C

题解

选 **C. i*i**。

因为一个大于 1 的合数一定有一个不超过它平方根的质因子，所以只需枚举到 i*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); ``

以 120 为例：

• i = 2：输出三个 2，n 变成 15。
• i = 3：输出一个 3，n 变成 5。
• i = 4：4*4 > 5，退出循环，最后输出 5。

注意：循环条件中的 n 会随着试除不断变小。