题解 P3383 【【模板】线性筛素数】

· · 题解

关于欧拉筛的原理其他几篇题解已经写的很清楚了，我只做一点小小的补充：这道题需要开一个长度为 1\times 10^8 的巨大数组，即便将数组类型设置为bool也需要很大的空间开销（超过110MB），而使用C++的bitset可以将空间的消耗减少到45MB左右，优化了近60%！

bitset可以近似看作bool数组，它的每个元素只占1位（bit），即一个字节（byte）的 \frac{1}{8}，并且可以单独访问、修改。使用bitset前需要包含头文件 <bitset>（当然万能头也是包含了这个的），定义bitset数组需要这样写：

bitset<100> b;//在<>内定义bitset的元素个数，b是这个bitset的名字

访问和修改的操作与bool数组类似，并且bitset还有很多强大的函数，这里和这里的两篇教程已经写的很详细了。

最后贴上代码：

#include <bits/stdc++.h>
//define mian main 别直接抄
using namespace std;
inline int read()
{
    int data = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')
            ch = getchar();
    while (ch >= '0' && ch <= '9')
    {
        data = (data << 3) + (data << 1) + ch - '0';
        ch = getchar();
    }
    return data;
}
void write(int f)
{
    if (f > 9)
        write(f / 10);
    putchar(f % 10 + '0');
}
const int maxn = 1e8 + 1;
bitset<maxn> num;
vector<int> prime;//vector并没有比数组慢多少
inline void init(int n)
{
    for (int i = 2; i <= n; ++i)
    {
        if (!num[i])
            prime.push_back(i);
        for (int j = 0; j < prime.size(); ++j)
        {
            if (i * prime[j] >= n)
                break;
            num[i * prime[j]] = 1;
            if (i % prime[j] == 0)
                break;
        }
    }
}
int mian()
{
    int n = read(), q = read(), x;
    init(n);
    while (q--)
    {
        x = read();
        write(prime[x - 1]);
        putchar('\n');
    }
    return 0;
}