完善程序（第一题）：线性筛素数

ri216530 组合题 共 个子题

下面的程序使用线性筛（欧拉筛）计算 2 到 n 之间（含 n）素数的个数。线性筛保证每个合数只被它的最小质因子筛去一次，因此时间复杂度为 O(n)。试补全程序。

#include <cstdio>

const int MAXN = 1000005;
bool isComp[MAXN];
int prime[MAXN];
int pcnt = 0;

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 2; i <= n; ++i) {
        if (___①___) {
            prime[++pcnt] = i;
        }
        for (int j = 1; j <= pcnt && ___②___; ++j) {
            isComp[___③___] = true;
            if (___④___) {
                ___⑤___
            }
        }
    }
    printf("%d\n", pcnt);
    return 0;
}

子题 单选题

①处应填（ ）

A

!isComp[i]

B

isComp[i]

C

isComp[i] == false && i > 2

D

prime[i] == 0

子题 单选题

②处应填（ ）

A

prime[j] <= n

B

i * prime[j] <= n

C

i * prime[j] < n

D

j <= n

子题 单选题

③处应填（ ）

A

i + prime[j]

B

prime[j] * prime[j]

C

i * prime[j]

D

i * j

子题 单选题

④处应填（ ）

A

i % prime[j] != 0

B

prime[j] > i

C

i == prime[j]

D

i % prime[j] == 0

子题 单选题

⑤处应填（ ）

A

isComp[i] = true;

B

--j;

C

break;

D

continue;

正在加载题目数据…
已答 /
子题
该题型需在试卷/作业中作答，单题练习暂不支持
答案解析
讨论
发布
登录后参与讨论 立即登录
发布讨论需先绑定并验证手机号 去绑定手机号
加载中…
我
我
回复 @
回复 @
发送
还没有人讨论，来发表第一条吧