算法简介：骑士团长的一日假期

素数筛法是作为数论基础而出现的。数论本质上是对数字的一些性质的研究，而质数是这里很重要的一部分。不同的质数筛有着不同的特性，用来解决不同的题目，接下来我们会大概了解几种。

算法演示：若困你于无风之地

$O(\sqrt n)$ 判断单个质数

这个很简单，由于考虑到因子是一对一对的，所以一对因数中较小的那一个最多最多是 $\sqrt n$ ，也就是说我们只需要枚举 $2$ ~ $\sqrt n$ 复杂度 $O(\sqrt n)$ ，不枚举 $1$ 是因为所有数字都是 1 的倍数，素数也只是被 $1$ 和它本身整除。

bool isPrime(int x) {
    if(x <= 1) return false;
    for(int i = 2; i * i <= n; i++) {
        if(x % i == 0) return false; // 找到一个不是 1 也不是它本身的因子
    }
    return true;
}

$O(n\log\log n)$ 多个快筛

这个就属于新开一篇了，我们大概的思考一下，什么东西不是质数，如果已知不等于一的数字，他除了自己以外的倍数一定都是合数，这样的话可以写出如下代码：

int flag[N]; // 是不是质数（是 - 0， 否 - 1）
flag[1] = 1;
for(int i = 2; i <= N; i++) {
    for(int j = i + i; j <= N; j += i) {
        flag[j] = 1;
    }
}

这样的话我们会发现有大量的复杂度浪费，一个数字，它会被他所有的因子（注意是所有的，不论质数还是合数）筛一遍，这是不优秀的。所以我们可以让质数去筛合数，这样就没有问题了。

int flag[N]; // 是不是质数（是 - 0， 否 - 1）
flag[1] = 1;
for(int i = 2; i <= N; i++) {
    if(flag[i]) continue; // 是合数，不要
    for(int j = i + i; j <= N; j += i) {
        flag[j] = 1;
    }
}

而复杂度的话，我们发现每次只用素数去筛，复杂度形如：$O(\cfrac n 2 + \cfrac n 3 + \cfrac n 5 + \dots)$ 而由于 $n$ 以内质数的量级大约是 $\log n$（准确点是 $\ln n$ ）然后又是类调和级数，估计复杂度为 $O(n\log\log n)$ 。

以上的筛法被称为埃氏筛。

$O(n)$ 线性筛

我们发现一个这里复杂度的瓶颈在于一个数会被他所有的素因子筛到，这个是不允许的，我们思考如何可以让一个数字只被他最小的素因子筛到。我们记录一个素数表存储已经记录好的素数。对于一个素数，他的倍数一定是合数，这样的话就只需要对于每次筛出来的素数和一个数相乘就可以了。

bool isprime[MAXN]; // isprime[i]表示i是不是素数
int prime[MAXN]; // 现在已经筛出的素数列表
int n; // 上限，即筛出<=n的素数
int cnt; // 已经筛出的素数个数
memset(isprime, true, sizeof(isprime)); // 先全部标记为素数
isprime[1] = false; // 1不是素数
for(int i = 2; i <= n; i++) { // i从2循环到n（外层循环）
    if(isprime[i]) prime[++cnt] = i;
    // 如果i没有被前面的数筛掉，则i是素数
    for(int j = 1; j <= cnt && i * prime[j] <= n; j++) {
        // 筛掉i的素数倍，即i的prime[j]倍
        // j循环枚举现在已经筛出的素数（内层循环）
        isprime[i * prime[j]] = false;
        // 倍数标记为合数，也就是i用prime[j]把i * prime[j]筛掉了
        if(i % prime[j] == 0) break;
        // 最神奇的一句话，如果i整除prime[j]，退出循环
        // 这样可以保证线性的时间复杂度
    }
}