第36552题 组合题
完善程序(第一题):线性筛素数

下面的程序使用线性筛(欧拉筛)计算 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;
}
{{ option.label }}
子题{{ index + 1 }} {{ child.type_label }}
{{ option.label }}
✓ 正确 ◐ 部分正确 ✗ 错误
程序运行统计
暂无判题统计
知识点:
提交{{ questionInfo.stats ? questionInfo.stats.submit_count : 0 }}次 正确率{{ statsAccuracy }}%
答案解析