线性筛选（欧拉筛选）-洛谷P3383

#include <bits/stdc++.h>
using namespace std;
int main()
{std::ios::sync_with_stdio(false); cin.tie(nullptr);		//为了加速int n, q;cin >> n >> q;				vector<int>num(n + 1);			//定义数字表vector<int>prime;			//定义素数表数组num[1] = 1, num[0] = 1;	//将0和1标记为非素数（用1表示）for (int i = 2; i <= n; i++){if (!num[i])	prime.push_back(i);		//如果素数（未被标记为1）往素数表后面添加该数for (auto p : prime)			//用p遍历素数表里面的数{if (i * p > n)	break;			//当发现i*p越界，则跳出，开始下一个inum[i * p] = 1;				//将合数（i*p)用1标记为非素数if (i % p == 0)	break;			//若p是i的最小质因数，则p也是合数（i*p）的最小质因数/*欧拉筛法规定一个合数只能被它最小的质因子筛去，i%prim[j]==0，代表prim[j]是i的因数，未来能被i的倍数筛掉的也一定能被prim[j]的倍数筛掉，所以需要提前退出循环。*/}}int number;while (q--){cin >> number;cout << prime[number - 1] << "\n";		//用\n换行节省时间}return 0;
}

参考：

欧拉筛法规定一个合数只能被它最小的质因子筛去，i%prim[j]==0，代表prim[j]是i的因数，未来能被i的倍数筛掉的也一定能被prim[j]的倍数筛掉，所以需要提前退出循环。

 欧拉筛，几行就行，一次就好_哔哩哔哩_bilibili

【数学】线性筛质数 (欧拉筛)_哔哩哔哩_bilibili

有关ios::sync_with_stdio(false)；和 cin.tie(nullptr)；的介绍与意义-CSDN博客