前置知識

埃氏篩素數、C++ 基礎。

閱讀程序

#include <bits/stdc++.h>
using namespace std;
int main(){int a1[51] = {0};int i,j,t,t2,n = 50;for(i = 2;i<=sqrt(n);i++){if(a1[i] == 0){t2 = n/i;for(j = 2;j<=t2;j++) a1[i*j] = 1;}}t = 0;for(i = 2;i<=n;i++){if(a1[i] == 0){cout <<" "<<i;t++;if(t%10 == 0) cout << endl;}}cout << endl;return 0;
}

判斷

1） 若把 $05$ 行 n 改為 $51$，程序可能發生運行時錯誤。()

2） 若去掉第 $04$ 行的 $\text{"={0}"}$，則程序運行結果不會改變。()

3） 這個程序輸出了 $16$ 個數字。()

4） 輸出的第 $11$ 個數為 $31$。()

選擇

5）程序的時間復雜度為( )

A $\text{O}(1)$ B $\text{O}(n)$ C $\text{O}(n\log n)$ D $\text{O}(n\log \log n)$

6）輸出的第 $14$ 個數為( )

A.$41$ B.$42$ C.$43$ D.$44$

答案解析

首先分析程序：程序使用埃氏篩素數的方法篩出了 $50$ 以內的所有素數，同時以每行 $10$ 個的方法進行輸出。

判斷

1）對

因為 $a$ 數組的大小為 $51$，C++ 規定數組只能訪問到 $\text{數組長度}?1$ 的下標位置，訪問 a[51] 時會出現下標越界的情況。

2）錯

int a[51]={0} 是一種初始化方法，因為在 main 函數中定義的所有變量（包括數組）內的初始值是不確定的，={0} 表示把數組內的元素全部初始化為 $0$（此操作也可以用 memset 實現）。如果去掉的話會影響運行結果。

3）錯

$50$ 以內的質數只有以下 $15$ 個：$2,3,5,7,11,13,17,19,23,29,31,37,41,43,47$

題目說輸出了 $16$ 個數字，所以是錯誤的。

4）對

如上題打的表所示，第 $11$ 個質數就是 $31$。

選擇

5）D

常識題，埃氏篩找出 $n$ 以內的素數的時間復雜度為 $\text{O}(n\log \log n)$；

普通篩質數的復雜度為 $\text{O}(n)$，優化后可達 $\text{O}(\sqrt{n})$；

線性篩法找出前 $n$ 個素數的的時間復雜度為 $\text{O}(n)$。

6）C

根據第 $4$ 題打的表，第 $14$ 個數是 $43$，所以選 C。

總結

以上為【CSP初賽練習】程序閱讀3 的習題解析，希望大家喜歡！

想要復制保存參見 Markdown 源代碼。