最近不做高精的题了，可能会多做一些动规的题，刚刚做了一道有关于线性筛质数的模板题，坑还是比较多的。
题目描述
知识链接
欧拉筛法
欧拉筛法（别称“欧拉筛”或“欧筛”），时间复杂度为O(n)。
欧拉筛法分为以下几步：
- 建立一个变量a，从2开始，如果数a并没有被标记为合数，那么将其加入到素数数组中。
- 之后开始去除合数，将a分别乘素数数组每一个数的积标记为合数。注意，重点来了：当素数数组中出现一个能够整除a的数时，直接结束去除合数，至于为什么，我现在也搞不太明白[汗]
- 重复以上步骤，每次a++，直到a=n。
关于欧筛的更多细节，可以参见欧拉线性筛法求素数(顺便实现欧拉函数的求值)_NK_test的博客-CSDN博客。
解题思路
此题的时间要求较为严格，数据较大，所以用普通的埃拉托斯特尼筛法（别称“埃氏筛”或“埃筛”，复杂度为O(n log n)）肯定是不行的，这时候我们就引出了一种较为复杂、但是极为快速的线性素数筛法——欧拉筛。至于欧筛的用法，上面已经讲述过了，总体来讲模板题还是比较简单的。
但是，如果你直接提交了下面的代码，会发现有两个点超时（想不到吧，我没有直接贴最终代码虚晃一枪）。
#include <array>
#include <iostream>
using namespace std;
array<bool, 100000010> _isVisd;
array<int, 1000010> _inquires;
array<int, 100000010> _primes;
void prime(int);
int main(void)
{
int n = 0, q = 0;
_isVisd.fill(false);
_inquires.fill(0);
_primes.fill(0);
cin >> n >> q;
for (int i = 0; i < q; i++)
{
cin >> _inquires[i];
}
prime(n);
for (int i = 0; i < q; i++)
{
cout << _primes[_inquires[i] - 1] << endl;
}
return 0;
}
void prime(int n)
{
int cnt = 0;
for (int i = 2; i < n; i++)
{
bool run = true;
if (!_isVisd[i])
{
_primes[cnt++] = i;
}
for (int j = 0; j < cnt && i * _primes[j] < n && run; j++)
{
_isVisd[i * _primes[j]] = true;
if (i % _primes[j] == 0)
{
run = false;
}
}
}
return;
}
顺带一提一个无伤大雅的小优化，这里使用的是先全部输入、处理后再输出的方式，如果将其改为处理后边输入边输出的方式，不仅代码更简洁，还可以省下一个大数组。只要删除_inquires数组的定义，然后将main函数“_primes.fill(0);”和“return 0;”之间的内容替换为如下代码即可：
cin >> n >> q; // 先输入n和q
prime(n); // 直接求素数
for (int i = 0; i < q; i++) // 边输入边输出
{
int ka = 0;
cin >> ka; // 输入要求的素数
cout << _primes[ka - 1] << endl; // 输出素数
}
言归正传，至于这个题它为什么会超时呢？按理说O(n)的复杂度已经足以应付这种程度的题了，所以我们先排除算法的问题。在排除可能的优化（不太清楚还能怎么优化）和代码本身的错误（几乎不可能，否则就会WA了）后，我将目光瞄准了输入输出。在将输入和输出更换为scanf和printf后，终于全部AC了。至于快速输入输出，一般来说没有这个必要，scanf和printf就可以了。
还有一些说法，说C++本身的执行速度就不如C，像这种说法肯定就是无稽之谈，甚至还有说Pascal执行速度比C更高一等。或许C的执行速度是比C++快上一点点，但我们就要为了这一点微乎其微的时间而放弃我们熟悉的语言吗？C比C++快的时间只体现在开发操作系统这种超大型工程软件上，在这种小小的OI题目上，C和C++的差别并不是很大。
另外，在程序前面加上一行代码，就可以使用cin和cout替代scanf和printf了，据测试速度不比scanf和printf，具体原理是啥我也不太清楚，可以看一下这篇博文：https://blog.csdn.net/qq_33248299/article/details/52144485。
ios::sync_with_stdio(false);
不过这样的坏处是用不了scanf和printf了（不过有cin、cout谁还会用scanf、printf呢）。但是，虽然在本地测试速度差不多，但放到洛谷上还有三个点TLE了，我估摸着应该是洛谷编译器的问题吧。所以我还是推荐大家用scanf和printf，毕竟万一哪天编译器抽风了，那就真的是“十年OI一场空”了。
代码展示
拒绝抄袭，共创和谐社会[机智]
#include <array> // std::array
#include <cstdio> // std::scanf, std::printf
using namespace std;
array<bool, 100000010> _isVisd; // 标记是否是合数
array<int, 100000010> _primes; // 素数数组
void prime(int); // 查找素数
int main(void)
{
int n = 0, q = 0;
_isVisd.fill(false); // 初始化，下同
_primes.fill(0);
scanf("%d %d", &n, &q); // 使用scanf快速输入
prime(n); // 有了n就可以直接求素数了
for (int i = 0; i < q; i++) // 边输入边输出
{
int ka = 0;
scanf("%d", &ka); // 输入
printf("%d\n", _primes[ka - 1]); // 输出，注意数组是从0开始的，所以要将k减一
}
return 0;
}
void prime(int n)
{
int cnt = 0; // 有几个不大于n的素数
for (int i = 2; i < n; i++) // i从2到n
{
bool run = true;
if (!_isVisd[i]) // 查看i是否是素数
{
_primes[cnt++] = i; // 将i加入素数数组
}
for (int j = 0; j < cnt && i * _primes[j] < n && run; j++) // 注意并不是只有i为素数时才标记合数
{
_isVisd[i * _primes[j]] = true; // 将i分别乘当前求出的素数，将其标记为合数
if (i % _primes[j] == 0) // 如果i能被当前素数整除
{
run = false; // 直接退出循环
}
}
}
return; // 还可以将函数改为int prime(int)，这样的话在这里可以返回cnt，cnt就是有几个不大于n的素数
}
写在最后
这道题并不算是难题，只不过有很多的坑点，尤其是输入输出，平常写程序推荐使用C++的cin和cout，但是算法竞赛时大家一定要养成使用scanf和printf进行输入输出的习惯，必要时候甚至要熟记快读快写的模板。