CSP-J 2024 入门级 第一轮（初赛） 阅读程序（1）

【题目】

CSP-J 2024 入门级 第一轮（初赛） 阅读程序（1）

1 #include <iostream>
2 using namespace std;
3
4 bool isPrime(int n) {
5 		if (n <= 1) {
6 			return false;
7 		}
8 		for (int i = 2; i * i <= n; i++) {
9 			if (n % i == 0) {
10 				return false;
11 			}
12 		}
13 		return true;
14 }
15
16 int countPrimes(int n) {
17 		int count = 0;
18 		for (int i = 2; i <= n; i++) {
19 			if (isPrime(i)) {
20 				count++;
21 			}
22 		}
23 		return count;
24 }
25
26 int sumPrimes(int n) {
27 		int sum = 0;
28 		for (int i = 2; i <= n; i++) {
29 			if (isPrime(i)) {
30 				sum += i;
31 			}
32 		}
33 		return sum;
34 }
35
35 int main() {
37 		int x;
38 		cin >> x;
39 		cout << countPrimes(x) << " " << sumPrimes(x) << endl;
40 		return 0;
41 }

判断题
1. 当输入为“10”时，程序的第一个输出为“4”，第二个输出为“17”。
2. 若将 isPrime(i)函数种的条件改为 i<=n/2,输入“20”时，countPrimes(20)的输出将变为“6”。
3. sumPrimes 函数计算的是从 2 到 n 之间的所有素数之和。
单选题
4. 当输入为“50”时，sumPrimes(50)的输出为（ ）
A.1060
B.328
C.381
D.275
5. 如果将 for(int i=2;i*i<=n;i++)改为 for(int i=2;i<=n;i++),输入“10”时，程序的输出（ ）
A.将不能正确计算 10 以内素数个数及其和
B.仍然输出4和17
C.输出3和 10
D.输出结果不变，但运行时间更短

【题目考点】

1. 循环：计数，求和

2. 函数

3. 质数判定

【解题思路】

isPrime函数判断传入的n是否是质数。
countPrimes函数统计1~n中的质数个数。
sumPrimes函数统计1~n中的质数加和。

【试题答案及解析】

判断题
1. 当输入为“10”时，程序的第一个输出为“4”，第二个输出为“17”。
答：T
1~10中质数有$2,3,5,7$，有4个。加和为$2+3+5+7=17$，叙述正确。

2. 若将 isPrime(i)函数中的条件改为 i<=n/2，输入“20”时，countPrimes(20)的输出将变为“6”。
答：F
由于$\frac{n}{2}\ge \sqrt{n}$，所以i从2循环到n/2和i从2循环到$\sqrt{n}$的最终效果是一样的。
输入20时，countPrimes函数返回的仍然是1~20中的质数个数，有$2,3,5,7,11,13,17,19$，共8个，应该输出8。该题叙述错误。

3. sumPrimes 函数计算的是从 2 到 n 之间的所有素数之和。
答：T
叙述正确。

单选题
4. 当输入为“50”时，sumPrimes(50)的输出为（ ）
A.1060
B.328
C.381
D.275
答：B
求1~50中的质数加和
$2+3+5+7+11+13+17+19+23+29+31+37+41+43+47=328$，选B。

5. 如果将 for(int i=2;i*i<=n;i++)改为 for(int i=2;i<=n;i++),输入“10”时，程序的输出（ ）
A.将不能正确计算 10 以内素数个数及其和
B.仍然输出4和17
C.输出3和10
D.输出结果不变，但运行时间更短
答：A
isPrime函数的内部原理为：
枚举从2到$\lfloor \sqrt{n}\rfloor$的所有整数，如果存在n的约数，那么n不是质数。如果不存在，则n是质数。
如果枚举从2到n的所有数字，那么当i为n时，一定有n%i == 0，isPrime函数一定会返回false，那么isPrime函数就失去了判断n是否为质数的功能，因此将不能正确计算10以内的质数个数和加和，选A。