这里是一条笔记，用于记录与素数相关的数论算法.

本题相当于求解前 $\pi(100)$ 个正素数，一个自然的想法是对每个小于等于 $n$ 的数进行一次质数检验，但这种暴力的做法显然不能达到最优复杂度.

下面介绍几种比暴力更优的素数筛法.

Eratosthenes 筛法

我们很容易发现一个事实：对于任意一个大于 $1$ 的正整数 $n$，它的 $x$ 倍是合数（$x>1$）.

利用这个事实，我们可以避免很多次不必要的检测.

如果我们从小到大考虑每个数，然后同时把当前这个数的所有（比自己大的）倍数记为合数，那么运行结束的时候没有被标记的数就是素数了.

并且，十分显然的是，要找到直到 $n$ 为止的所有素数，仅对不超过 $\sqrt n$ 的素数进行筛选就足够了.

其代码实现如下：

int isPrime[N];
void Eratosthenes(int n) {
    isPrime[0] = isPrime[1] = 0;
    for (int i = 2; i <= n; i ++) {
        isPrime[i] = 1;
    }
    for (int i = 2; (long long)i * i <= n; i ++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j ++) {
                isPrime[j] = 0;
            }
        }
    }
    return;
}

以上就是 Eratosthenes 筛法（埃拉托斯特尼筛法，简称埃氏筛法）的内容，其时间复杂度是 $O\left(n\log\log n\right)$.

以下是对于其时间复杂度的证明：

$\mathbf{Proof.}$

如果每一次对数组的操作花费 $1$ 个单位时间，则时间复杂度为：

$$O\left(\sum_{k=1}^{\pi\left(\lfloor\sqrt n\rfloor\right)}\dfrac n{p_k}\right)=O\left(n\sum_{k=1}^{\pi\left(\lfloor\sqrt n\rfloor\right)}\dfrac1{p_k}\right) $$

其中 $p_k$ 表示第 $k$ 小的素数，$\sum_{k=1}^{\pi\left(\lfloor\sqrt n\rfloor\right)}$ 表示第一层 for 循环，$\dfrac n{p_k}$ 表示第二层 for 循环的执行次数. 根据 Mertens 第二定理，存在常数 $B_1$，使得：

$$\sum_{k=1}^{\pi\left(\lfloor\sqrt n\rfloor\right)}\dfrac1{p_k}=\log\log\lfloor\sqrt n\rfloor+B_1+O\left(\dfrac1{\log\lfloor\sqrt n\rfloor}\right) $$

所以 Eratosthenes 筛法的时间复杂度为 $O\left(n\log\log n\right)$. 接下来证明 Mertens 第二定理的弱化版本，即

$$\sum_{k\leqslant\pi(n)}\dfrac1{p_k}=O\left(\log\log n\right) $$

根据 $\pi\left(n\right)=\Theta\left(\dfrac n{\log n}\right)$，可知第 $n$ 个素数的大小为 $\Theta\left(n\log n\right)$. 于是就有

$$O\left(\sum_{k=1}^{\pi(n)}\dfrac1{p_k}\right)=\displaystyle O\left(\sum_{k=2}^{\pi(n)}\dfrac1{k\log k}\right)=O\left(\displaystyle \int_2^{\pi(n)}\dfrac{\mathrm dx}{x\log x}\right)=O\left(\log\log\pi\left(n\right)\right)=O\left(\log\log n\right) $$$$\mathfrak{Q.E.D.}$$

由时间复杂度可知，上述做法仍然不够高效.

但是我们很容易考虑到，只需要筛选奇数就可以，因为除了 $2$ 以外的偶数都是合数，且除了 $3$ 以外的能被 $3$ 整除的数一定是合数，所以我们可以直接跳过它们，只用关心 $3$ 以外的奇数就好.

线性筛法

埃氏筛法仍有优化空间，它会将一个合数重复多次标记.

有没有什么办法省掉无意义的步骤呢？答案是肯定的.

如果能让每个合数都只被标记一次，那么时间复杂度就可以降到 $O\left(n\right)$ 了.

其代码如下：

int notPrime[N], prime[N], num = 0;
void Euler(int n) {
	for (int i = 2; i <= n; i ++) {
	    if (!notPrime[i]) {
		    prime[num ++] = i;
	    }
	    for (int j = 0; j < num; j ++) {
		    if (i * prime[j] > n) {
			    break;
  			}
		    notPrime[i * prime[j]] = 1;
		    if (i % prime[j] == 0) {
			    break;
  			}
        }
	}
    return;
}

上面的这种线性筛法也称为 Euler 筛法（欧拉筛法）.