共48道题，当前是第29题

初赛真题

01 #include <iostream>
02 using namespace std;
03 
04 const int N = 1e6 + 5;
05 
06 int n, cnt, Prime[N];
07 bool Vis[N];
08 
09 int main()
10 {
11     cin >> n;
12     for (int i = 2; i <= n; i++)
13     {
14         if (!Vis[i])
15             Prime[++cnt] = i;
16         for (int j = 1; j <= cnt && (long long)i * Prime[j] <= n; j++)
17         {
18             int k = i * Prime[j];
19             Vis[k] = true;
20             if (i % Prime[j] == 0)
21                 break;
22         }
23     }
24     cout << cnt;
25     return 0;
26 }
假设输入的 n 是小于 N 的正整数,请回答下列问题


1. B。 因为 $n < N = 10^6 + 5$， 所以 $i * Prime[j]$ 一定在 int 范围内，故去掉强制转换答案依旧正确。
2. B。 $30$ 以内共有 $10$ 个质数。
3. A。 相同的清况已经被第 $20$ 行的 if(i% Prime[j] == 0) 给排序掉了。
4. D。 $20,21$ 行可以减少程序的运行时间，但不影晌答案。
5. C。 $100$ 以内共有 $25$ 个质数。
6. A。 时间复杂度为 O(n)。

Question

1. 如果删去了第 16 行的强制类型转换 (long long)，输出的结果会发生变化（）

2. 当输入的 n 为 30 时，输出为 11（）

3. 第 18 行得到的所有的 k 互不相同（）

4. 下列做法不可能改变程序的结果的是（）

5. 下列 n 的取值中，输出的结果为 25 的是（）

6. 这份代码的时间复杂度为 （）