一、相關概念

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

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

素數的分布很不均勻，下表部分列出了小于 $x$ 的素數個數函數 $p_i(x)$。

x$p_i(x)$

10	4
100	25
1,000	168
10,000	1,229
100,000	9,592
1,000,000	78,498
10,000,000	664,579
100,000,000	5,761,455
1,000,000,000	50,847,534
10,000,000,000	455,052,511
100,000,000,000	4,118,054,813
1,000,000,000,000	37,607,912,018
10,000,000,000,000	346,065,536,839
100,000,000,000,000	3,204,941,750,802
1,000,000,000,000,000	29,844,570,422,669
10,000,000,000,000,000	279,238,341,033,925
100,000,000,000,000,000	2,623,577,157,654,233
1,000,000,000,000,000,000	24,739,954,287,740,860
10,000,000,000,000,000,000	234,057,667,276,344,607
100,000,000,000,000,000,000	2,220,819,602,560,918,840

二、素數的判定

方法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; }

---

方法2：
這個方法是對方法1的改進，我們知道如果一個數為合數，那么它可以分解為兩個相等的數或者一小一大的兩個數相乘。例如 $16$ 可以表示為 $2?8$，也可以表示為 $4?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; }

需要注意的一點是，很多人因為貪圖方便，喜歡把上面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需要小于nll a = rand() % (n - 2) + 2;//如果不滿足費馬小定理，則n不是素數if (quick_pow(a, n - 1, n) != 1) return 0;}return 1; }

三、求素數

接下來將給出三種求一系列素數（素數表）的方法，三種方法各有優劣，下面以求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; }

優點：程序邏輯簡單、容易理解，適合新手學習。
缺點：算法效率較低，如果要求前 $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?2$ 開始 $2$ 的倍數全部劃掉。接著我們走到下一個沒有被劃掉的數（素數） $3$，我們同樣將寫的數中從 $3?3$ 開始 $3$ 的倍數全部劃掉……

• 以此類推，我們依次訪問沒有被劃掉的數 $i$，得到我們要求的素數，同時將從 $i?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，這種方法的效率已經有了質的提升，而且也不會很難理解。

缺點：同一個合數有可能會被重復劃去，例如 $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;//關鍵處1for (ll j = 1; j <= cnt && i * prime[j] <= n; j++) {isNotPrime[i * prime[j]] = 1;//關鍵處2if (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可以知道，相比埃氏篩，線性篩在處理篩除時，無論 $i$ 是素數還是合數都會參與篩除過程。（下面 $p_j$ 即為代碼中的 $prime[j]$）

• 如果 $i$ 是素數，本次篩掉的是 $i?p_j$ ，其中 $p_j$ 是小于或等于 $i$ 的素數。
• 如果 $i$ 是合數，本次篩掉的 $i?p_j$ 中， $p_j$ 表示的是小于或等于 $i$ 的最小質因數的素數。關鍵處2保證的就是 $p_j$ 不大于 $i$ 的最小質因數。

部分篩除過程如下表：

2x2
2x3	3x3
2x4
2x5	3x5	5x5
2x6
2x7	3x7	5x7	7x7
2x8
2x9	3x9
2x10
2x11	3x11	5x11	7x11	11x11

（還不懂可以參悟一下這個表~）

優缺點總結：

• 線性篩沒有冗余，不會重復篩除同一個數，時間復雜度為線性，是最快的一種素數篩法，也是打素數表的最佳選擇。
• 相比前面兩種算法，這種算法沒有那么容易理解，很多人都只是選擇背模板。

參考資料

Eratosthenes篩法(埃式篩法)時間復雜度分析

信息學奧賽之數學一本通

線性篩素數（歐拉篩）（主要學習了證明）

---

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

• 點贊，這是對作者辛苦寫作的最低成本的鼓勵。
• 答應我，把它學會！（別扔進收藏夾吃灰）
• 可以考慮關注一波，算法系列的文章會持續更新。

總結

以上是生活随笔為你收集整理的求素数的方法完整归纳，学的不仅是“求素数”！的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。