#include <iostream>
using namespace std;
int main() {
const int N = 30;
bool p[31] = {false}; // p[i]=true 表示 i 是合数
for (int i = 2; i * i <= N; i++)
if (!p[i])
for (int j = i * i; j <= N; j += i) p[j] = true;
int c = 0;
for (int i = 2; i <= N; i++) if (!p[i]) c++;
cout << c << endl;
return 0;
}
- (1) 程序输出结果是______。（4 分）
- (2) 该程序使用的算法名称是______。（4 分）
- (3) 该算法的时间复杂度约为______。（5 分）
答案解析
（1）2~30 间素数有 2,3,5,7,11,13,17,19,23,29 共 10 个，输出 10。（2）埃拉托斯特尼筛法（素数筛法）。（3）时间复杂度约 O(N log log N)。