思路

题意：多组询问，每次给出 $n \in [2, 10^6]$，输出所有不超过 $n$ 的质数；询问数量不固定，读到文件结束为止。

算法：一次筛，多次查表

如果每次询问都重新判定质数，最坏复杂度是 $O(n\sqrt{n})$，无法承受。注意到所有询问的上界都是 $10^6$，可以把“每个数是否为质数”预先算好，之后每组询问只做一次 $O(n)$ 的扫描输出。

采用埃拉托斯特尼筛：

1. 令 p[i] = 1，再把 p[0] = p[1] = 0；
2. 顺序枚举 $i$，若 p[i] 为假说明它已被更小的质因子筛掉，跳过；
3. 否则 $i$ 是质数，把 $2i, 3i, \dots$ 全部标为合数。

正确性

• 合数 $j$ 必有真因子 $i \ge 2$，当外层枚举到 $i$ 时，$j$ 作为 $i$ 的倍数（且 $j \ge 2i$）被标记，所以合数一个不漏；
• 被标记的位置一定存在真因子，故都是合数，质数不会被误标；
• 因此筛后 p[i] 恰为 $i$ 是否质数。

多组输入的处理

主函数用 while(cin >> n) 循环读入，直到没有更多数据为止，这正好对应“输入包含多组数据、组数未给出”的要求。每组调用 go() 输出答案并换行，组与组之间没有多余空行。

筛的上界取 N = 2e6 + 10，比题目上限 $10^6$ 大出一倍以上，保证 i*2 之类的下标不会越界。注意第 0、1 位被预先置为 0，所以实际输出范围是 $[2, n]$。

复杂度

• 预处理：时间 $O(N\log\log N)$，空间 $O(N)$，只做一次；
• 每组询问：$O(n)$ 遍历输出。

总输出量可能达到数 MB，因此关闭了 cin/cout 的同步，避免 I/O 成为瓶颈。

代码

#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 = 2e6+10;   // 覆盖题目上限 1e6 并留出余量
int p[N];               // p[i] 为 1 表示 i 是质数

// 埃氏筛：一次预处理，标记 [0, N) 内的质数
void pre(){
    fill(p, p+N, 1);
    p[0] = p[1] = 0;
    for(int i=0;i<N;i++){
        if(!p[i])continue;      // 合数已被筛掉，跳过

        // 标记 i 的所有倍数为合数
        for(int j=i*2;j<N;j+=i){
            p[j] = 0;
        }
    }
}
int n;
void go(){
    
    // 输出不超过 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();              // 预处理只在程序开始时做一次
    // 组数由 EOF 决定，题目不先给出 T，因此不读组数
    while(cin>>n){      // 多组数据，读到文件结束
        go();
    }
    return 0;
}