思路与算法

把0和1标为非素数，2到n暂标为素数。枚举仍是素数且ii不超过n的i，从ii开始按步长i标记合数。递增输出全部剩余素数，每个一行。

正确性说明

被标记的数是i的倍数且至少为ii，有非平凡因子，所以不可能误删素数。任一合数x有一个不超过sqrt(x)的素因子p，x至少为pp，在处理p时必被删掉。因此所有剩余数恰是素数，递增遍历满足排序和完整性。

复杂度

初始化和输出各O(n)，埃氏筛标记O(n log log n)，总时间O(n log log n)，空间O(n)。n在2至1000范围内。

易错点

1不是素数，筛表边界包含n。标记从i*i开始，不能从i自身开始。输出全部质数且每个一行，不输出个数，也不是第n小的素数。

参考代码（C++11）

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<bool> prime(n + 1, true);
    prime[0] = prime[1] = false;
    for (int i = 2; i * i <= n; ++i)
        if (prime[i])
            for (int j = i * i; j <= n; j += i)
                prime[j] = false;
    for (int i = 2; i <= n; ++i)
        if (prime[i])
            cout << i << '\n';
}