求素数的方法完整归纳，学的不仅是“求素数”！

一、相关概念

定义：素数（Prime Number）又称质数，是指大于1且只能被1和它本身整除的正整数，例如2，3，5，7，11等。

与素数相对的就是合数，它能被一个本身之外的数整除，例如4，6，8，9等。注意：1既不是素数也不是合数。

素数的分布很不均匀，下表部分列出了小于 $x$ 的素数个数函数 $p_i(x)$。

二、素数的判定

方法1：
这种方法是基于素数的定义的判定，也是新手最容易想到的一种方法。只要正整数 $n$ 不能被区间 $[2,n)$ 中的整数整除，那么它满足素数的素数的定义，即 $n$ 是素数。（注意，$2$ 需要特判），算法的时间复杂度为$O(n)$。

int isPrime(int n) {
    if (n == 2) return 1;
    for (int i = 2; i < n; i++)
        if (n % i == 0) return 0;
    return 1;
}
1
2
3
4
5
6

---

方法2：
这个方法是对方法1的改进，我们知道如果一个数为合数，那么它可以分解为两个相等的数或者一小一大的两个数相乘。例如 $16$ 可以表示为 $2\ast 8$，也可以表示为 $4\ast 4$。

因此，我们只要正整数 $n$ 不能被区间 $[2,\sqrt{n})$ 中的整数整除，就可以断定 $n$ 为素数，算法的时间复杂度就降到$O(\sqrt{n})$。这种方法也是我们最常用的判断方法。

int isPrime(int n) {
    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0) return 0;
    return 1;
}
1
2
3
4
5

需要注意的一点是，很多人因为贪图方便，喜欢把上面i <= sqrt(n)写成i*i <= n。这样虽然也没有错，但是如果要判定的数接近 $\sqrt{2^{31}-1}$ 就很容易爆int，导致答案错误。

---

方法3：
这种方法名为Miller-Rabin素性测试，主要用于判定比较大的数（通常大于 $10^9$ ）是否为素数，算法时间复杂度为 $O(tlogn)$ （其中，$t$ 为测试次数），通常是在程序设计竞赛中出现，非竞赛选手可以不用掌握。

Miller-Rabin素性测试需要用到快速幂和费马小定理，这里就不做详细介绍，后面的博客也会写到。需要注意的是，Miller-Rabin素性测试检测出来的素数有可能能是非素数！ $n$一次通过测试，则 $n$ 不是素数的概率为25%；如果通过 $t$ 次测试，则 $n$ 不是素数的概率为 $\frac{1}{4^t}$。因此，在保持效率的同时也需要兼顾正确率。

typedef long long ll;
/**
  * 快速幂函数
  * a为底数，n为指数，mod为模数
  */
ll quick_pow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n) {
        if (n & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        n >>= 1;
    }
    return res;
}
/**
  * Miller_Rabin素性测试
  */
int Miller_Rabin(ll n) {
    if (n == 2) return 1;
    //测试次数的选取需要适当
    for (int i = 0; i < 10; i++) {
    	//随机数a需要小于n
        ll a = rand() % (n - 2) + 2;
        //如果不满足费马小定理，则n不是素数
        if (quick_pow(a, n - 1, n) != 1) return 0;
    }
    return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

三、求素数

接下来将给出三种求一系列素数（素数表）的方法，三种方法各有优劣，下面以求1000以内的素数为例进行讲解。

方法1：
利用上面素数判定的方法2进行判定，将判定为素数的数存进素数表中，这种方法通常用在求比较小的素数的时候，时间复杂度 $O(n\sqrt{n})$。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 205;
int cnt, prime[maxn];
/**
  * 素数的判定函数
  */
int isPrime(int n) {
    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0) return 0;
    return 1;
}
int main()
{
    for (int i = 2; i <= 1000; i++)
        if (isPrime(i)) prime[++cnt] = i;
    printf("%d\n", cnt); //输出素数个数
    for (int i = 1; i <= cnt; i++)
        printf("%d ", prime[i]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

优点：程序逻辑简单、容易理解，适合新手学习。
缺点：算法效率较低，如果要求前 $10^5$ 个素数时，算法便无法在 $1s$ 内完成。

---

方法2：
这种素数的筛选法称为Eratosthenes筛法（埃拉托斯特尼筛法，简称埃氏筛），算法的时间复杂度为 $O(nlogn)$ 。相对来说还是比较好理解的，下面我们以求 $[1,n]$ 中的素数为例进行讲解：

• 我们就先把1，2，3，4，5，6，7，8，9，10，11，12，……，n-1，n 的在纸上先写出来。

• 由于我们知道1既不是素数也不是合数，所以先把1给划掉。

• 然后我们走到 $2$，发现 $2$ 没被划掉，说明 $2$ 是素数，于是我们在写的数中从 $2\ast 2$ 开始 $2$ 的倍数全部划掉。接着我们走到下一个没有被划掉的数（素数） $3$，我们同样将写的数中从 $3\ast 3$ 开始 $3$ 的倍数全部划掉……

• 以此类推，我们依次访问没有被划掉的数 $i$，得到我们要求的素数，同时将从 $i\ast i$ 开始的 $i$ 倍数全部划掉，最后那些没有被划掉的数都是我们要求的素数！

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1010;
int cnt, prime[maxn], isNotPrime[maxn];
/**
  * Eratosthenes筛法，求n以内的素数
  */
void getPrime(int n) {
    isNotPrime[0] = 1;
    isNotPrime[1] = 1;
    for (ll i = 2; i <= n; i++)
        if (!isNotPrime[i]) {
            prime[++cnt] = i;
            //把i的倍数都标记为不是素数
            for (ll j = i * i; j <= n; j += i)
                isNotPrime[j] = 1;
        }
}

int main()
{
    getPrime(1000);
    printf("%d\n", cnt); //输出素数个数
    for (int i = 1; i <= cnt; i++)
        printf("%d ", prime[i]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

优点：相比方法1，这种方法的效率已经有了质的提升，而且也不会很难理解。

缺点：同一个合数有可能会被重复划去，例如 $12$ 会被 $i=2$ 和 $i=2$时划去，影响效率。

---

方法3：
这中素数的筛选法叫做欧拉筛，因为该算法对于合数有且只会筛除一次，所以常将其称为线性筛，时间复杂度为 $O(n)$ 。

算法的核心思想： 对于每一个数（无论素数，还是合数）$i$，筛掉所有小于$i$最小质因子的质数乘以 $i$ 的数。代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1010;
int cnt, prime[maxn], isNotPrime[maxn] = {1, 1};
/**
  * 线性筛素数
  */
void getPrime(int n) {
    for (ll i = 2; i <= n; i++) {
        if (!isNotPrime[i]) prime[++cnt] = i;
        //关键处1
        for (ll j = 1; j <= cnt && i * prime[j] <= n; j++) {
            isNotPrime[i * prime[j]] = 1;
            //关键处2
            if (i % prime[j] == 0) break;
        }
    }
}
int main()
{
    getPrime(1000);
    printf("%d\n", cnt); //输出素数个数
    for (int i = 1; i <= cnt; i++)
        printf("%d ", prime[i]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

可能看了上面的代码很多人还是没有理解，不过没关系，我们还会继续讲解。

由上面代码的关键处1可以知道，相比埃氏筛，线性筛在处理筛除时，无论 $i$ 是素数还是合数都会参与筛除过程。（下面 $p_j$ 即为代码中的 $prime[j]$）

• 如果 $i$ 是素数，本次筛掉的是 $i\ast p_j$ ，其中 $p_j$ 是小于或等于 $i$ 的素数。
• 如果 $i$ 是合数，本次筛掉的 $i\ast p_j$ 中， $p_j$ 表示的是小于或等于 $i$ 的最小质因数的素数。关键处2保证的就是 $p_j$ 不大于 $i$ 的最小质因数。

部分筛除过程如下表：

（还不懂可以参悟一下这个表~）

优缺点总结：

• 线性筛没有冗余，不会重复筛除同一个数，时间复杂度为线性，是最快的一种素数筛法，也是打素数表的最佳选择。
• 相比前面两种算法，这种算法没有那么容易理解，很多人都只是选择背模板。

参考资料

1. Eratosthenes筛法(埃式筛法)时间复杂度分析
2. 信息学奥赛之数学一本通
3. 线性筛素数（欧拉筛）（主要学习了证明）

---

既然都看到就这里了，希望你可以做到以下三点哦：

• 点赞，这是对作者辛苦写作的最低成本的鼓励。
• 答应我，把它学会！（别扔进收藏夹吃灰）
• 可以考虑关注一波，算法系列的文章会持续更新。