$\Huge\color{orchid}{点击此处获取更多干货}$

质数筛

在不大于某一值的正整数范围内筛出所有的质数，很容易想到遍历该范围，判断每个数是不是质数的方法，结合之前判断质数的试除法，可以得知这样做时间复杂度为$O(n^{\frac{3}{2}})$。在比较大的范围比如$10^6$数量级之下，这样的复杂度就会显得很高，下面介绍两种比较常用的，能在更短的时间内筛出一定范围内质数的方法。

两种质数筛，用的是和哈希函数类似的结构体仿函数，并且都封装了质数$(\text{primes})$列表和每个数是否为合数$(\text{isComposite})$的信息，它们都由下面的抽象结构体继承而来：

/**
 * @brief 质数筛基类
 * 埃氏筛和欧拉筛都需要继承此基类的数组成员isComposite和primes（可以见名知意）
 */
struct Sieve {
    int* isComposite = nullptr;
    int* primes = nullptr;
    size_t size = 0;
    ~Sieve() {
        delete[] isComposite, primes;
    }
    virtual size_t operator()(int n) = 0;//纯虚函数，可以避免它的实例化
};

埃氏筛

首先，按照之前的算术基本定理，以及质数的定义可得，上限为$N$的正整数范围内，质数一定会最先出现，且假设其中某个数$x$是质数，那么其中的数$k*x$，当$k$是大于1的正整数时，这些数就全都是合数了，因此其中一种方法便应运而生，这就是“埃拉托斯特尼筛”$\text{(Eratosthenes’s Sieve)}$，也叫“埃氏筛”

struct EratosSieve : Sieve {
    /**
     * @brief 统计不大于n的正整数中质数的个数
     * @param n 上限
     * @return 质数个数
     */
    size_t operator()(int n) {
        if (n <= 0) {                               //上限n必须大于1
            throw logic_error("The upper limit must be positive");
        }
        isComposite = new int[n + 1]();
        primes = new int[n];
        for (int i = 2; i <= n; i++) {
            if (isComposite[i]) {                   //已经是质数的跳过
                continue;
            }
            primes[size++] = i;                     //到此已能保证i是质数，将其加入质数列表
            for (int j = 2 * i; j <= n; j += i) {   //从2开始倍增i，去掉范围内每一个合数k*i
                isComposite[j] = 1;
            }
        }
        return size;
    }
};

这样做的时间复杂度可以降到$O(n*log(log(n)))$

欧拉筛

埃氏筛虽然已经获得了一定程度的效率提升，但中间仍然存在重复统计的情况，比如24在$i=2$的时候就通过$k=12$筛选掉了，但是在$i=3$的时候它通过$k=8$又筛了一次，有没有办法让这样的重复筛选现象消失呢？答案是有的，这里换一种方式，不再确保遇到的是质数之后再倍增，而是每当遇到一个数，都用它来为小于它的所有质数倍增，直到遇上了能整除它的某个质数为止，这就是“欧拉筛”$\text{(Euler’s Sieve)}$.

struct EulerSieve : Sieve{
    size_t operator()(int n) {
        if (n <= 0) {
            throw logic_error("The upper limit must be positive");
        }
        isComposite = new int[n + 1]();
        primes = new int[n];
        for (int i = 2; i <= n; i++) {
            if (!isComposite[i]) {                  //是质数的保存，但不是质数的不跳过
                primes[size++] = i;
            }
            for (int j = 0; j < size; j++) {
                if (i * primes[j] > n) {            //越界跳过
                    break;
                }
                isComposite[i * primes[j]]++;       //倍增
                if (i % primes[j] == 0) {           //遇上了能整除它的另一个质数时，直接跳出
                    break;
                }
            }
        }
        return size;
    }
};

最后花点时间解释一下，为什么当前的数能被另一个质数整除时，是“直接跳出”：
当中间存在某个$i\%primes[j]=0$时，后面的$i*primes[j+1]$就可以用另一种方式得到，假设它为$x*primes[j]$；
对于$i$来说，$primes[j]$是它的质因数，并且由于primes表的单调增加性质，这个primes[j]是$i$的最小质因数；
假设$i=m*primes[j]$，则有$x*primes[j]=i*primes[j+1]=m*primes[j]*primes[j+1]$，这个$x$就可以是$m*primes[j+1]$，在后面用$x$为列表里的质数倍增的时候会将$i*primes[j+1]$作为合数筛掉
$j+2,j+3,…,size-1$的情况都类似