素数是一种作业或竞赛中较易考察的知识点，但好像在实际开发中用的不多【素数好像更多地用在网安领域】。总归，求取 a~b 之间的素数还是一种比较基本的算法技巧。

新手求素数

想当年，我刚学C语言的时候，便是这么写的，也就是直接暴力枚举：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int count;
int prime[MAX_N]; 

void getPrime(int a, int b) {
    count = 0;
    int j;
    for (int i = a; i <= b; ++i) {
        for (j = 2; j < i; ++j) {
            if (i % j == 0) break;
        }
        if (j == i)
            prime[count++] = i;
    }
}

那时的我也还想到了比如 2*3=6 和 3*2=6 是等价的，所以判断素数的终止条件可以再压缩，也就是：

1
for (j = 2; j < i/2; ++j)

知道点啥之后

后来我在看过某本书的序言之后，知道了只需要检测到 \(\sqrt i\) 即可，可以将这种算法的时间复杂度可以进一步压缩 ，也就是

1
for (j = 2; j <= sqrt(b); ++j)

注意引入：math.h

素数筛

素数筛，顾名思义，就是将素数筛出来，而比较常见的有两种：

Eratosthenes筛法

埃氏筛是比较基本的一种筛法，其思想是：在处理掉所有不是质数的数（质数的倍数），然后，剩下的便全都是素数了。

1
2
3
4
5
6
7
8
9
10
void getPrime() {
    vector<bool> flag(b, true);

    for (int i = 2; i <= b; ++i) {
        if (!flag[i]) continue;
        for (int j = i*2; j <= b; j += i) {
            flag[j] = false;
        }
    }
}

常见的埃氏筛都是返回一个布尔类型的数组，来得知是否质数的。

虽然此举将时间复杂度降为了 \(O(N log log N)\)，但是可以发现，埃氏筛依旧具有重复操作，比如 12 在被 2 置 false 之后，还会被 3 置一遍，于是便有了改进之法。

欧式筛法

欧式筛可以看作埃氏筛的一个改进，即不做重复操作，保证所有合数都是由其最小质因数标记的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool flag[MAX_N] = {false};
int prime[MAX_N] = {0};

void getPrime() {
    int count = 0;
    for (int i = 2; i <= b; ++i) {
        if (!flag[i]) {
            prime[count++] = i;
        }
        for (int j = 0; j < count && i*prime[j] <= b; ++j) {
            flag[i*prime[j]] = true;
            if (i % prime[j] == 0) break;
        }
    }
}

因为 C++ 的 bool 数组默认均为 false，所以索性用 false 标记质数（0和1在上述代码中并未置数为 false）。而最终的结果，储存在 prime 之中。

时间复杂度为：\(\omega (N)\)

总结

可以发现，随着时间复杂度的降低，空间复杂度好像在升高了，尤其体现在两个筛法的实现之中。