PDF文档公众号回复关键字:20240727
2020 CSP-J 完善程序1
1 完善程序 (单选题 ，每小题3分，共30分)
质因数分解给出正整数 n，请输出将 n 质因数分解的结果，结果从小到大输出
例如：输入 n=120，程序应该输出 2 2 2 3 5，表示：120 = 2 ×2 ×2 ×3 ×5
输入保证2<=n<=10^9
提示：先从小到大枚举变量 i，然后用 i 不停试除 n来寻找所有的质因子
01 #include <cstdio>
02 using namespace std;
03 int n, i;
04 int main() {
05 scanf("%d", &n);
06 for(i = ①;② <=n;i ++){
07 ③{
08 printf("%d ", i);
09 n = n / i;
10 }
11 }
12 if(④)
13 printf("%d ", ⑤);
14 return 0;
15 }
34.①处应填( ) [3分]
A.1
B.n-1
C.2
D.0
35.②处应填( C ) [3分]
A.n/i
B.n/(i*i)
C.i*i
D.iii
36.③处应填( ) [3分]
A.if(n%i==0)
B.if(i*i<=n)
C.while(n%i==0)
D.while(i*i<=n)
37.④处应填( ) [3分]
A.n>1
B.n<=1
C.i<n/i
D.i+i<=n
38.⑤处应填( ) [3分]
A.2
B.n/i
C.n
D.i
2 相关知识点
1) 质数 (Prime Number)
一个大于1的自然数，除了1和它本身以外不再有其他因数的数称为质数
例如
2、3、5、7、11、13、17、19等都是质数
注意
质数只有两个正因数：1和它本身
2) 因数
因数是指能整除给定正整数的数
例如，8的因数有1、2、4、8，因为这些数都能整除8
3) 质因数
质因数是指能整除给定正整数且是质数的因数
例如，36的质因数是2和3，因为36=2×2×3×3，这里的2和3都是质数
4) 质因数分解
每个合数都可以写成几个质数相乘的形式.
其中每个质数都是这个合数的因数一个，合数用几个质数相乘的形式表示出来,叫做分解质因数
例如
12=2x2x3
5) 质因数分解朴素算法
#include <cstdio>
using namespace std;
int n, i;
int main(){scanf("%d", &n);for(i =2;i<=n;i ++){//从质数2开始 去试除 /*一个质数可能试除多次 比如12 =2 *2 *3 ,其中2需要试除2次 */ while(n%i==0){C++printf("%d ", i);n = n / i;}}return 0;
}
6) 质因数分解优化
朴素算法从2到n试除过程中需要试除n-1次
实际试除sqrt(n)次即可
n不可能有2个大于sqrt(n)的质因数
证明 - 发证法
1质因数相乘还是n的因数，因数一定是<=n的
2如果2个因数都大于sqrt(n),那这2个因数相乘必然大于n
因此1和2是矛盾的，所以如下结论成立
n不可能有2个大于sqrt(n)的质因数
7) 优化后质因数分解
#include <cstdio>
using namespace std;
int n, i;
int main(){scanf("%d", &n);for(i =2;i*i<=n;i ++){//从质数2开始 去试除 /*一个质数可能试除多次 比如12 =2 *2 *3 ,其中2需要试除2次 */ while(n%i==0){printf("%d ", i);n = n / i;}}/*优化后情况 有可能n为i ,i*i<=n判断不成立例如 12 -- 分解2 2 后剩余3 此时 i*i=3*3 n为3不成立，少输出1次 */if(n>1) printf("%d ", n);//此时的n为对为最后一个质数 return 0;
}
3 思路分析
34.①处应填( C ) [3分]
A.1
B.n-1
C.2
D.0
分析
质数从2开始，逐一试除，不会出现输出合数的情况
例如20=2 * 2 * 5
2去试除，剩余5
3去试除，4去试除，此时，4已经被因子2分解了
5去试除
35.②处应填( C ) [3分]
A.n/i
B.n/(i*i)
C.i*i
D.i* i * i
分析
n不可能有2个大于sqrt(n)的质因数
所以枚举试除到sqrt(n) 即可
36.③处应填( C ) [3分]
A.if(n%i==0)
B.if(i*i<=n)
C.while(n%i==0)
D.while(i*i<=n)
分析
如果i去试除n，如果可以整除，则分解掉i
可能出现到多次试除，直到把i都分解掉掉
例如
12=2 * 2 * 3
其中2被分解2次
37.④处应填( A ) [3分]
A.n>1
B.n<=1
C.i<n/i
D.i+i<=n
分析
优化后情况 有可能n为i ,i*i<=n判断不成立
例如 12 -- 分解2 2 后剩余3 此时 i*i=3*3 n为3不成立，少输出1次
此时需要判断n是否分解完所有质数，如果n>1,说明还有质因子没分解完
38.⑤处应填( C ) [3分]
A.2
B.n/i
C.n
D.i
分析
同37题
主要和i*i<=n 有关，可能会漏调一个i的判断
例如
12 =2 * 2 * 3
2去试除，可以把2个2分解掉
此时3去试除，面临判断i*i<=n 即 3 * 3 <=3判断，不成立，会漏掉3 (此时n为3)
例如如下情况即不存在这种情况
36 = 2 * 2 * 3 * 3
2去试除，可以把2个2分解掉
此时3去试除，面临判断i*i<=n 即 3 * 3 <=9判断，条件成立，会把2个3分解掉
所以只可能漏调一个质因数，并且此时n为对应质因数
