這是個好問題（狗頭）

質數

人類對數論的研究可以追溯到公元前，在數論研究的悠久歷史中，質數是一個永恆的話題。對於質數的判定，也永遠是一個迷人的問題。

我們這樣定義質數：如果自然數 p &> 1 的因數只有1和它本身，那麼 p 是質數。

質數有很多美妙的性質，比如：

  • 如果一個數是質數，那麼它是自然數。
  • 如果一個數是質數，那麼它不是合數。
  • 如果一個數是質數，那麼它大於等於2。

相信我們聰明的讀者不難證明這些性質。

接下來，讓我們進入正題：如何判定一個數是不是質數？

入門版

素數判定這種高深的數論問題，用一般的編程語言肯定難以優雅地實現。所以，我們必須使用 Wolfram Language 這樣專門用於數學計算的語言，才能寫出「出淤泥而不染，濯清漣而不妖」的美妙實現。

你是素數嗎 = PrimeQ;

我們來看一個例子：

這種純粹的感覺，就像在QQ羣裏at你的同學一樣自然！

但是，我們不能沉溺於舒適區，要勇於面對自己，我們要前往混沌邪惡的 C++ 領域。

初級版

在進入這一章節之前，我們需要一些十分複雜的數論推導，不喜歡看公式的同學可以暫時跳過下面一小段。

要判斷一個數是不是質數，其實和判斷一個數是不是合數沒有太大區別。要判斷一個數是合數，按照定義來看，只需要找到一個不是1和它本身的因數就可以。如果我們對一個數 n，找到了這樣的因數 m，也就是 m 整除 n，此時一定會有 [公式] 。所以，我們只需要在 2~n-1 的範圍內尋找 n 的因數就可以了。

上面的推導中居然出現了整整一個公式！我這篇回答的讀者要跑掉一半了！

根據上面的數論推導，我們可以寫出如下的質數判斷程序：

bool 你是質數嗎(int n) {
if (n &<= 1) return false; for(int i = 2; i &< n; ++i) if (n % i == 0) return false; return true; }

在這裡，我們約定負數和0不是質數。

看 C++ 這混沌邪惡的語法，反人類的 for 循環，甚至連 bool 都只是語法糖，在輸出的時候只能給出一個冷冰冰的 0 和 1，一點不考慮用戶體驗……

高級版

在上面的演算法中，我們需要窮舉2~n-1的所有整數。真的就沒有改進方法了嗎？

在古希臘時期，有一位數學家叫埃拉託斯特尼，提出了一種方法，叫做埃拉託斯特尼篩法。埃拉託斯特尼篩法是非常經典的質數判定演算法，在各種要求精確解的質數判定中，大多數都能見到埃拉託斯特尼篩法的影子。在這裡，我必須多次重複埃拉託斯特尼這個長的要命的名字，以表達我對埃拉託斯特尼這位偉大先賢的崇高敬意。埃拉託斯特尼篩法的思想可以給我們很大的啟發，埃拉託斯特尼篩法指導我們進一步縮小因數的搜索範圍。

為此，我們仍然需要更加複雜的數論推導。

對於合數 n，我們可以證明它一定有一個小於等於 [公式] 的非平凡因數。這裡的非平凡因數，指的是和1與他本身不同的因數。

如果不是，那麼它所有的非平凡因數都是大於 [公式] 的。我們任取其中一個和n不同的非平凡因數 m，那麼存在整數 k 使 n=km，那麼 k 也為 n 的非平凡因數，但是 [公式] ，矛盾。所以合數 n 一定有一個小於等於 [公式] 的非平凡因數。

到現在為止我已經用了5個公式了！我的讀者已經只剩1/32了！

因此，我們只需要在2到 [公式] 之間尋找 n 的因數。（這裡的 [公式] 表示不超過 x 的最大整數。）

不對，我怎麼又用了兩個公式……

bool 你是質數嗎(int n) {
if (n &<= 1) return false; for(int i = 2; i * i &<= n; ++i) if (n % i == 0) return false; return true; }

超極版

我們剛才的演算法都是按照質數的定義，去找一個數有沒有因數，這種做法太 naive 了。

那麼，有沒有什麼能判定質數的高級定理呢？

為了寫這篇文章，我耗費了整整180秒上網查資料，找到了這麼一個定理：

威爾遜定理：對於自然數 p&>1，p 是質數當且僅當 [公式] 。

我怎麼又用了公式！還用了同餘符號！我的讀者會全跑掉的啊！

按照上面的想法，我們只要求出 [公式] 除以 p 的餘數，看看是不是0就好了。

bool 你是質數嗎(int n) {
if (n &<= 1) return false; int factor = 1; for(int i = 2; i &< n; ++i) factor = ((long long)factor * i) % n; factor = (factor + 1) % n; return factor == 0; }

等等，這個演算法好像比上面兩個都要慢啊！

速度什麼不重要，重要的是讓別人知道了我們能熟練運用威爾遜定理這樣高級的數論定理。

還有，那個說在項目裏這麼寫代碼的會被人打死的站出bubyguoi;ohugkbvfdsvvgrt4u

上D版

上D與你同在

感謝上D把我復活，我又能回來寫文章了。

剛才的方法，無一例外都是基於簡單的數論原理，這種人工設計的演算法難以發揮計算機真正的性能。

我們要逃脫手工設計演算法的桎梏，進入機器學習的神聖殿堂。

於是我又花了整整200秒去查找資料，終於在一篇知乎回答中找到了實現方法：

能否使用神經網路來判斷奇偶數？?

www.zhihu.com圖標

作者使用了端到端的雙層 LSTM 網路，將數字轉為字元串輸入，在質數判定問題上進行了1分鐘的訓練，效果拔羣。

神經網路學會了「不管你輸入啥只要我蒙合數總比蒙質數對的多」。

按照這一思想，我們得出了一個對幾乎全部自然數正確的質數判定演算法：

bool 你是質數嗎(int n) {
return false;
}

多麼簡潔的邏輯！機器學習讓我們發現了世界的本質，就是大道至簡！只要我們願意捨棄那麼一（億）點點正確性，一切都是如此簡單！

撒D版

歡迎來到D獄

上D的演算法沒能給我們很大的幫助，但是這種思想給了我們一點啟發：

演算法的能力是有極限的。我從短暫的 OI 生活當中學到一件事：越是玩弄優化，就越會發現演算法被時間複雜度所限制……除非超越演算法。

你到底想說什麼？

我不做人了，JOJO！（劃去）我不要精確度了！

於是我們祭出了費馬小定理：如果 p 是素數，那麼有 [公式] 。

雖然費馬小定理的逆命題是不成立的，但是不排除它在絕大多數情況下都是成立的。為了方便計算，取 a=2，於是我們又得出了一個對幾乎全部自然數正確的質數判定演算法：

bool 你是質數嗎(int n) {
if (n &<= 1) return false; int t = 1, m = 2, p = n; while(p) { // 快速冪取模 if (p % 2) t = ((long long)t * m) % n; m = (m * m) % n; p &>&>= 1;
}
t = (t - 2) % n;
return t == 0;
}

這個演算法的速度相比之前的演算法，完全不在一個數量級上，只是精確度稍微差了那麼一（億）點點。比如經典的卡邁克數561，它雖然是合數（561=3×11×17），但是會被這個演算法判定為質數。

但是，如果我們對這一演算法進行一（億）點點改進，就能得到大名鼎鼎的 Miller-Rabin 素性檢驗演算法[1]。這一演算法在費馬小定理之外，還需要另一個更加複雜的數論定理：

二次檢驗定理：對於質數 p，在0~p-1範圍內，滿足 [公式] 的整數只有 1 和 p-1。

證明就留做習題吧。

根據二次檢驗定理，對於一個整數 x，如果 [公式] 除以 n 的餘數都不為1，那麼 n 就很有可能是一個質數。

然後我們再把費馬小定理換個形式，如果 [公式] 除以 n 的餘數為1，那麼 n 很可能是一個質數。

接下來，就是撒D賜予我們的鬼才邏輯了。首先把 n-1 分解為 [公式] ，接著再把 [公式] 不斷平方，每平方一次，進行一次二次檢驗，這樣平方 s 次之後，恰好就求出了 [公式] 。

int prime[10]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
bool 你是質數嗎(int n) {
if (n &<= 1) return false; if (n == 2) return true; int s = 0, t = n - 1; while (!(t % 2)) ++s, t &>&>= 1; // 求解 n-1=2^s*t
for (int i = 0; i &< 10 prime[i] &< n; ++i) { int a = prime[i]; int b = 1, m = a, p = t; while (p) { //快速冪，求 b=a^t if (p % 2) b = ((long long) b * m) % n; m = ((long long)m * m) % n; p &>&>= 1;
}
if (b == 1) continue;
for (int j = 1; j &<= s; ++j) { // 進行 s 次二次檢驗 int k = ((long long)b * b) % n; if(k == 1 b != n-1) return false; b = k; } if (b != 1) return false; } return true; }

這裡選取了前10個質數作為底，已經可以規避絕大多數的誤檢情況。

最後的最後

也許質數檢驗這一個問題並不像它看上去的那麼簡單。在它的背後，蘊含著深刻的數學原理。2002年，來自印度坎普爾理工學院的計算機科學家，Manindra Agrawal、Neeraj Kayal和Nitin Saxena，發表了論文 PRIMES is in P[2]，提出了第一個一般的、確定性的、不依賴未證明命題的多項式時間素數判定演算法，作者們也因此獲得了哥德爾獎和富爾克森獎。回觀這篇文章中提到的演算法，每一次進步都離不開跳出框架局囿的創新思考。要敢於打破那些固有認知中的限制。也許哪一天，用神經網路判別質數這樣看起來根本不可能的想法，也會變成現實呢。

參考

  1. ^Hurd J. Verification of the Miller–Rabin probabilistic primality test[J]. The Journal of Logic and Algebraic Programming, 2003, 56(1-2): 3-21.
  2. ^Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P", Annals of Mathematics 160 (2004), no. 2, pp. 781–793.

用篩法即可！

這個問題你首先應該自己想，或者去查書，或者問度娘。

老夫當前在蹲馬桶無聊，就答一下吧。你拿從 2 到 根號n 一個個去試除 n，即 i 從 2 到 根號n，n/i 有一個除盡就是合數，一個都除不盡n就是質數。

直接看代碼

https://github.com/Zi-Gao/Small-Tools?

github.com

這是整個項目

關於質數檢測的是

https://github.com/Zi-Gao/Small-Tools/blob/master/primeNumberDetection.java

最簡單的辦法：從1除到n

改進一點：從2除到根號n

再改進一點：先構造一個素數表，然後只除表裡的數。

只能被1，和自身整除，不能被其它自然數整除。

判斷n是不是質數，

輸入n，

定義b大於1，小於n。

判斷

n除1餘數等於0

n除n餘數等於0

n除以b不等於0

判斷成立時，n是質數。

我不知道這個「其它自然數」怎麼定義

所以就把「其它自然數」定成大於1，小於n。

是否正確，還有待驗證，百度又查不到。

推薦閱讀：
相關文章