CSP 2020 入门组第一轮 第19题:质因数分解

2021年8月24日 | 分类: 【编程】

CSP 2020 入门组第一轮 第19题

【题目】

(质因数分解)给出正整数 n,请输出将 n 质因数分解的结果,结果从小到大输出。 例如:输入 n=120,程序应该输出 2 2 2 3 5,表示:\(120=2\times2\times2 \times3\times5\)。输入保证 \(2\leq{n}\leq {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;
}

1)①处应填( C )
2)②处应填( C )
3)③处应填( C )
4)④处应填( A )
5)⑤处应填( C )

1.
    A.    1
    B.    n-1
    C.    2
    D.    0
2.
    A.    n/i
    B.    n/(i*i)
    C.    i*i
    D.    i*i*i
3.
    A.    if(n%i==0)
    B.    if(i*i<=n)
    C.    while(n%i==0)
    D.    while(i*i<=n)
4.
    A.    n>1
    B.    n<=1
    C.    i<n/i
    D.    i+i<=n
5.
    A.    2
    B.    n/i
    C.    n
    D.    i

【解析】

质数的判断是:

for(int i=2; i*i<=n; i++){}

不停试除,直到结果不能被i整除:

while(n%i==0){}

最后如果 \(n\leq1\),那么结果就没必要输出,所以:

if(n>1){ cout<<n; }

参考:https://www.cnblogs.com/hellohebin/p/15110990.html