思路

题意：给定 $n \le 10^3$，输出所有不超过 $n$ 的质数，同一行内用空格分隔。

算法：埃拉托斯特尼筛

数据范围很小（$n \le 1000$），直接筛出 $[0, N)$ 内所有整数是否为质数即可，且只需在程序开始时筛一次。

筛法要点：

1. 初始时令 p[i] = 1（全部假设为质数），再把 p[0] = p[1] = 0，因为 0 和 1 都不是质数；
2. 从 i = 0 顺序扫描，若 p[i] 为假说明 $i$ 已被更小的质因子筛掉，直接跳过；
3. 否则 $i$ 是质数，把所有 $\ge 2i$ 的 $i$ 的倍数标记为合数（p[j] = 0）。

内层从 2i 开始而不是从 i*i 开始，虽然多做了一些重复标记，但正确性不受影响，且对于 $N=10^3$ 的开销可以忽略。

为什么正确

• 每个合数 $j$ 都有真因子 $i \ge 2$，当外层扫描到 $i$ 时 $j \ge 2i$ 会被标记为合数；
• 反过来，被标记的位置一定是某个 $i$ 的倍数且 $j \ne i$，必为合数；
• 因此筛完后 p[i] 为真当且仅当 $i$ 是质数。

输出细节

go() 中读入 $n$ 后，从 $i=0$ 遍历到 $n$，只输出 p[i] 为真的下标。由于 p[0] = p[1] = 0，实际上等价于输出 $[2, n]$ 中的质数。每个数后面带一个空格，最后统一换行；题目对行末多余空格不敏感。当 $n < 2$ 时不会输出任何质数，只输出一个空行。

复杂度

一次预处理时间为 $O(N \log\log N)$（只有质数 $i$ 会进入内层循环，循环总次数为 $\sum_{i \text{ prime}} N/i \approx N\log\log N$），空间 $O(N)$。每组询问输出为 $O(\pi(n) + n)$，在本题规模下可以忽略。

代码

#include<bits/stdc++.h>
#define int long long
#define dd double
#define str string
#define el cout << '\n'
#define re return
#define ff first
#define ss second
#define pll pair<int,int>
#define pdd pair<dd,dd>
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;

const int N = 1e3+10;   // 略大于题目上限 1e3，留出安全边界
int p[N];               // p[i] 为 1 表示 i 是质数

// 埃氏筛：预先标记 [0, N) 内每个数是否为质数
void pre(){
    fill(p, p+N, 1);
    p[0] = p[1] = 0;    // 0 和 1 不是质数
    for(int i=0;i<N;i++){
        if(!p[i])continue;   // 已被更小的质数筛掉

        // 把 i 的所有倍数标记为合数
        for(int j=i*2;j<N;j+=i){
            p[j] = 0;
        }
    }
}

void go(){
    int n;cin>>n;
    // 输出 [0, n] 中所有质数（0、1 已被标记为非质数）
    for(int i=0;i<=n;i++){
        if(p[i]){
            cout<<i<<' ';
        }
    }
    el;

}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int _=1;
    pre();          // 只筛一次，之后每组数据直接查表
    // 本题只有一组数据；若需要多组输入，应在此处读入组数 T
    while(_--){
        go();
    }
    return 0;
}