个人笔记

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e6;
int q[N], n;

void eratos(int n) {
    memset(q, 0, sizeof q);

    for (int i = 2; i <= n; i ++) {
        if (q[i]) continue;
        else cout << i << endl;

        for (int j = i; j <= n / i; j ++) {
            q[i * j] ++;
        }
    }

    return;
}

int main() {
    cin >> n;

    eratos(n);

    return 0;
}

时间复杂度：$O(n \log \log n)$
注意标记时可以优化：$(x, x^2)$范围内不用再标记。证明如下：

假设 $k$ 是一个整数，且 $x < k < x^2$。
那么 $k$ 可以表示为 $k = x \cdot m$，其中 $m$ 是一个整数且 $1 < m < x$。由于 $m < x$，在埃氏筛法的执行过程中，$m$ 会先于 $x$ 被标记为素数或合数。
如果 $m$ 是素数，则在标记 $m$ 的倍数时，$k = x \cdot m$ 已经被标记为合数。
因此，当 $x$ 被处理时，$(x, x^2)$ 范围内的所有 $x$ 的倍数已经被标记过了，不需要再进行标记。

输出的是$i$，不要再手滑写成$q[i]$了