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

题目

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. if(n%i==0)
• B. if(i*i<=n)
• C. while(n%i==0)
• D. while(i*i<=n)

答案

C

题解

选 C：while(n%i==0)。

同一个质因子可能出现多次，所以要用 while 反复除以 i，直到不能整除为止。

例如 n=120、i=2 时：

• 输出 2，n 变成 60；
• 输出 2，n 变成 30；
• 输出 2，n 变成 15。

此时 15 不能被 2 整除，才继续枚举下一个 i。如果用 A 的 if，只会除一次，就会漏掉重复的质因子。

因此③处填： ``cpp while (n % i == 0) ``