线性时间枚举素数 – 数论方法

综述

枚举区间 $\scriptsize [l, h]$ 内的所有素数问题，方法及时间复杂度如下

方法	思想	时间	空间	素数表
枚举试除	逐个除余判断素数	$\scriptsize O(n\sqrt n)$	$\scriptsize O(n)$	仅有素数判别表
E-筛法	剔除所有质因子枚举的合数	$\scriptsize O(n\log \log n)$	$\scriptsize O(n)$	仅有素数判别表
欧拉筛法	剔除最小质因子枚举的合数	$\scriptsize O(n)$	$\scriptsize O(2n)$	判别表和纯素数表

枚举试除

枚举区间中每个数并判断素数：枚举从 $\scriptsize 2$ 到 $\scriptsize n$ 的所有因子，求模判断是否为所给数因数

优化

仅需枚举到较小的因子上界即可，上界为$\scriptsize \sqrt n$

bool isPrime(int n) {
    if(n <= 1) return false;
    for(int i = 2; i * i <= n; i++)
        if(n % i == 0) return false;
    return true;
}

vector<int> enumeration(int l, int h) {
    vector<int> v;
    for(int i = l; i <= h; i++)
        if(isPrime(i)) v.push_back(i);
    return v;
}

Eratosthenes-筛法

区间中枚举所有合数，筛掉所有合数则剩余的数均为素数

每个合数均可分解为 有限个质因子的乘积，依次筛掉所有质因子的倍数，则仅剩质因子本身

筛出区间 $\scriptsize [2,h]$ 内的素数，再挑选 $\scriptsize [l,h]$ 的素数

详细说明

从 $\scriptsize 2$ 开始一趟筛去所有 $\scriptsize 2N$ ，一趟筛去所有 $\scriptsize 3N$，一趟筛去所有 $\scriptsize 5N$，… ，依次向后筛，剩余序列一定为素数序列 $\scriptsize 2,3,5,7,11,…$，理由如下

区间中某数 $\scriptsize a$ ，在一趟区间遍历中筛去 $\scriptsize [2,h]$ 中因子为 $\scriptsize a$ 的所有合数 $\scriptsize Na (N>1)$，以 $\scriptsize a$ 为因子的数仅剩 $\scriptsize a$

设 $\scriptsize n \subseteq N$，则 $\scriptsize na \subseteq Na $，无需再筛 $\scriptsize na$ 的倍数，因为因子为 $\scriptsize na$ 的合数均已被筛

剩余的 $\scriptsize a$ 若为合数必定已被之前的因子筛掉，$\scriptsize Na$ 也必定被筛掉，因此此方法区间内剩余的数均为素数

每个合数要被筛 合数的不同质因子个数 次，共需筛 $\scriptsize n/2 + n/3 + n/5 + … = n\log \log n$ 次

优化

枚举合数因子时，到 $\scriptsize \sqrt n$ 即可枚举出 $\scriptsize \leqslant n$ 的所有合数

枚举合数时，后续枚举的 $\scriptsize (a+i)a$ 已被 $\scriptsize a(a+i)$ 枚举过，为避免重复从 $\scriptsize (a+i)^2, (a+i)(a+i+1), …$ 继续枚举

优化后仍有重复，如 $\scriptsize 2 \times 6 = 3 \times 4$

const int maxn = 1000000;
bool isPrime[maxn];

void enumeration(int l, int h) {
    memset(isPrime, true, sizeof(isPrime));

    for (int i = 2; i * i <= h; i++)
        if (isPrime[i])
            for (int j = i * i; j <= h; j += i)
                isPrime[j] = false;

    for (int i = l; i <= h; i++)
        if (isPrime[i])
            printf("%d", isPrime[i]);
}

欧拉线性筛法

E-筛法中根据合数的每个质因子筛出合数，因而合数重复筛了质因子个数次。

欧拉筛法仅 根据最小质因子筛出合数，因而每个合数仅被筛一次，时间复杂度降为 $\scriptsize O(n)$。

详细说明

依次筛掉所有质因子的倍数，则仅剩质因子本身，依次枚举 $\scriptsize N\times a(N \in [2,n])$ 并筛出，其中 $\scriptsize a$ 为已知质数，则剩余数为新确定的已知质数，继续枚举筛出、继续确定，…，具体过程如下

N	已知质数	筛出合数
2	2	4
3	2, 3	6, 9
4	2, 3	8
5	2, 3, 5	10, 15, 25
6	2, 3, 5	12
7	2, 3, 5, 7	14, 21, 28, 35

对照上表，以下解释每个合数仅被筛一次的原因。如果枚举 $\scriptsize 4 \times a$ 时取到 $\scriptsize a = 3$，枚举 $\scriptsize 6 \times a$ 时取到 $\scriptsize a = 2$，合数 $\scriptsize 12$ 将被最小质因子 $\scriptsize 2$ 和次小质因子 $\scriptsize 3$ 各乘出一次导致重复。这是因为 $\scriptsize 4$ 是 $\scriptsize 12$ 的因子，所以 $\scriptsize 12$ 的最小质因子应该是 $\scriptsize 4$ 的最小质因子 $\scriptsize 2$ ，其对应最小质因子分解为 $\scriptsize 6 \times 2$ ，而不是次小质因子分解 $\scriptsize 4 \times 3$。因此枚举因子 $\scriptsize N=4$ 只有 $\scriptsize 4 \times 2 = 8$ 可保证枚举乘积的最小质因子仍为 $\scriptsize 2$，与所有非最小质因子的乘积都不是最小质因子分解，都将会导致后续重复筛出。

因此枚举的因子 $\scriptsize N$ 为合数时仅与本身的最小质因子相乘，枚举的因子为质数时仅与不大于本身的质因子相乘，这就保证了枚举的唯一性。因此应依次模运算检测 $\scriptsize N$ 是否包含质因子表中的最小质因子、次小质因子、…，以保证每个枚举出的合数 $\scriptsize Na$ 都只被其最小质因子筛出，都只被枚举一次

Q： 既然是枚举质因子，可否优化到 $\scriptsize O(\sqrt n)$

A： 不能。枚举素数算法下界是区间中素数的个数 $\scriptsize O(\theta)$，表示每个素数仅计算一次得出，其中 $\scriptsize \theta$ 近似于 $\scriptsize n/\ln n > \sqrt n$。其次：① 线性筛法始终满足 $\scriptsize N \geqslant a$ ② 线性筛法枚举的是 最小质因子的分解 。枚举到 $\scriptsize N$ 时基于①无法取到更大的质数$\scriptsize N’ (n > N’ > N)$，基于②区间内的 $\scriptsize N’a$ 均无法被枚举筛出。如枚举 $\scriptsize [0, 100]$ 素数，当 $\scriptsize N = 10$ 时，$\scriptsize 11, 13, 17, …$ 的倍数均未被枚举。因此，达到 $\scriptsize N = n/2$ 时才可保证区间所有合数筛完，此时 $\scriptsize isPrime$ 判别表填写完成，算法已经可以停止。之后遍历到 $\scriptsize n$ 仅仅是为了填写完成纯素数表 $\scriptsize a$，此表的索引 $\scriptsize i$ 即是第 $\scriptsize i$ 个素数的序号，便于依据序号查找素数；若需要纯素数表时，也无需重新遍历判别表

const int maxn = 1e6;
bool isPrime[maxn];
int a[maxn];

void enumeration(int l, int h) {
    int composite, cnt = 1;
    memset(isPrime, true, sizeof(isPrime));

    for (int N = 2; N <= h; N++) {
        if (isPrime[N]) a[cnt++] = N;
        for (int i = 1; i < cnt; i++) {
            if ((composite = N * a[i]) > h) break;
            isPrime[composite] = false;
            if (N % a[i] == 0) break;
        }
    }

    for (int i = l; i <= h; i++)
        if (isPrime[i])
            printf("%d", isPrime[i]);
}