下面的程序使用线性筛(欧拉筛)计算 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;
}