1. 從一道題說(shuō)起為什么判定質(zhì)數(shù)值得深究最近在AcWing上刷題又碰到了那道經(jīng)典的866題——試除法判定質(zhì)數(shù)。題目本身是個(gè)模板題要求很簡(jiǎn)單給定n個(gè)正整數(shù)對(duì)于每個(gè)數(shù)判斷它是否是質(zhì)數(shù)。很多朋友尤其是剛開(kāi)始接觸算法競(jìng)賽或者準(zhǔn)備面試的朋友可能會(huì)覺(jué)得這題太基礎(chǔ)了不就是寫(xiě)個(gè)循環(huán)從2除到sqrt(x)嗎有什么好講的我剛開(kāi)始也是這么想的直到后來(lái)在真實(shí)的項(xiàng)目開(kāi)發(fā)、性能優(yōu)化甚至是一些安全相關(guān)的場(chǎng)景里反復(fù)被“如何高效、正確地判斷一個(gè)數(shù)是否為質(zhì)數(shù)”這個(gè)問(wèn)題“教育”。比如在生成RSA密鑰對(duì)時(shí)需要尋找大質(zhì)數(shù)在一些哈希算法或者隨機(jī)數(shù)生成器的底層質(zhì)數(shù)判斷是基礎(chǔ)操作甚至在處理一些看似簡(jiǎn)單的業(yè)務(wù)邏輯比如給商品分配唯一ID時(shí)如果設(shè)計(jì)不當(dāng)?shù)托У馁|(zhì)數(shù)判斷也可能成為性能瓶頸。這道題之所以經(jīng)典正是因?yàn)樗鼊冸x了復(fù)雜的外殼直指算法最核心的兩個(gè)訴求正確性和效率。而“試除法”作為最直觀的解法恰恰是理解這兩個(gè)訴求的絕佳起點(diǎn)。今天我們就以C實(shí)現(xiàn)為例不滿足于“AC”這道題而是深挖一下“試除法判定質(zhì)數(shù)”這個(gè)操作。我會(huì)帶你看看最樸素的寫(xiě)法有什么坑如何一步步優(yōu)化到競(jìng)賽和工程中常用的“優(yōu)化版試除法”并解釋清楚每一個(gè)優(yōu)化步驟背后的數(shù)學(xué)原理和性能考量。你會(huì)發(fā)現(xiàn)即使是一個(gè)for循環(huán)里面也大有文章。2. 質(zhì)數(shù)判定的核心理解試除法的本質(zhì)在動(dòng)手寫(xiě)代碼之前我們必須先搞清楚我們要解決的問(wèn)題究竟是什么。質(zhì)數(shù)素?cái)?shù)的定義是在大于1的自然數(shù)中除了1和它自身外不能被其他自然數(shù)整除的數(shù)。根據(jù)定義最直接的判斷方法就是“試除”嘗試用所有可能的小于它的數(shù)去整除它如果都除不盡它就是質(zhì)數(shù)。這個(gè)思路對(duì)應(yīng)到算法上就是一個(gè)典型的枚舉算法。我們枚舉所有可能的因子i(從2開(kāi)始)檢查x % i 0是否成立。一旦成立說(shuō)明找到了一個(gè)因子x就不是質(zhì)數(shù)如果枚舉完所有可能的i都沒(méi)有找到因子那么x就是質(zhì)數(shù)。這里立刻引出了第一個(gè)關(guān)鍵問(wèn)題我們需要枚舉到多少或者說(shuō)i的上界是多少一個(gè)常見(jiàn)的錯(cuò)誤是枚舉到x-1。這顯然效率極低對(duì)于一個(gè)大數(shù)來(lái)說(shuō)是不可接受的。我們需要利用數(shù)學(xué)性質(zhì)來(lái)縮小枚舉范圍。定理如果x是一個(gè)合數(shù)那么它必定有一個(gè)不大于sqrt(x)的質(zhì)因子。這個(gè)定理是試除法優(yōu)化的基石。我們來(lái)簡(jiǎn)單證明一下假設(shè)x是合數(shù)那么它可以分解為兩個(gè)因子a和b即x a * b。不妨設(shè)a b。那么a * a a * b x所以a sqrt(x)。也就是說(shuō)那個(gè)較小的因子a一定小于等于x的平方根。因此我們只需要檢查從2到sqrt(x)的整數(shù)中是否存在x的因子即可。如果在這個(gè)范圍內(nèi)都找不到因子那么x就是質(zhì)數(shù)。這就將枚舉范圍從O(x)縮小到了O(sqrt(x))這是一個(gè)巨大的優(yōu)化。例如判斷10^9是否是質(zhì)數(shù)只需要枚舉大約31622次而不是10^9次?；谶@個(gè)理解我們可以寫(xiě)出第一版“樸素試除法”的代碼框架bool is_prime(int x) { if (x 2) return false; // 質(zhì)數(shù)定義要求大于1 for (int i 2; i x / i; i) { // 循環(huán)條件i sqrt(x) 用 i x/i 避免溢出和浮點(diǎn)數(shù)運(yùn)算 if (x % i 0) return false; } return true; }注意循環(huán)條件i x / i。這是一個(gè)非常巧妙且安全的寫(xiě)法。它等價(jià)于i sqrt(x)但避免了使用sqrt函數(shù)帶來(lái)的浮點(diǎn)數(shù)精度問(wèn)題和可能的性能開(kāi)銷雖然現(xiàn)代編譯器優(yōu)化后差別不大更重要的是它完全在整數(shù)域內(nèi)運(yùn)算避免了i*i可能導(dǎo)致整數(shù)溢出的風(fēng)險(xiǎn)當(dāng)x接近int最大值時(shí)i*i可能會(huì)溢出。注意這里有一個(gè)初學(xué)者極易混淆的點(diǎn)。循環(huán)的終止條件是i x / i而不是i x / i。為什么需要等于考慮x4的情況。sqrt(4)2。我們需要檢查i2因?yàn)? % 2 0。如果條件是i x/i即i 4/22那么循環(huán)根本不會(huì)進(jìn)入i2不會(huì)被檢查程序會(huì)錯(cuò)誤地將4判定為質(zhì)數(shù)。所以這個(gè)等號(hào)至關(guān)重要。3. 效率進(jìn)階優(yōu)化枚舉的步長(zhǎng)上面的代碼已經(jīng)是一個(gè)正確的試除法實(shí)現(xiàn)了。對(duì)于AcWing866這樣的模板題輸入規(guī)模n在100以內(nèi)每個(gè)數(shù)x在2^31?1以內(nèi)這個(gè)算法完全夠用時(shí)間復(fù)雜度是O(n * sqrt(x))。但是如果我們追求極致的效率或者x本身非常大我們還能再優(yōu)化嗎答案是肯定的。我們還可以從減少枚舉次數(shù)上做文章。觀察一下我們枚舉的序列2, 3, 4, 5, 6, 7, 8, 9, 10, ...。作為一個(gè)合數(shù)如果它不能被2整除那么它肯定也不能被4、6、8、10等所有偶數(shù)整除。換句話說(shuō)除了2以外所有偶數(shù)都不可能是質(zhì)數(shù)因?yàn)樗鼈冎辽儆幸蜃?。那么我們?cè)诿杜e時(shí)是不是可以跳過(guò)所有的偶數(shù)呢這就是第一個(gè)優(yōu)化特判2然后從3開(kāi)始每次循環(huán)步進(jìn)2i 2只檢查奇數(shù)。優(yōu)化后的代碼如下bool is_prime(int x) { if (x 2) return false; if (x 2) return true; // 單獨(dú)判斷2 if (x % 2 0) return false; // 排除所有偶數(shù) for (int i 3; i x / i; i 2) { // 從3開(kāi)始每次加2 if (x % i 0) return false; } return true; }這個(gè)優(yōu)化直接將循環(huán)次數(shù)減少了一半因?yàn)榇蠹s一半的整數(shù)是偶數(shù)我們跳過(guò)了它們。這是一個(gè)非?？捎^的性能提升。那么還能更進(jìn)一步嗎可以。我們不僅想跳過(guò)偶數(shù)還想跳過(guò)那些明顯不是質(zhì)因子的數(shù)比如3的倍數(shù)除了3本身、5的倍數(shù)等等。這引出了“6n±1”法則。定理所有大于3的質(zhì)數(shù)都可以表示為6n ± 1的形式n為正整數(shù)。簡(jiǎn)單證明任何一個(gè)整數(shù)都可以表示為6n, 6n1, 6n2, 6n3, 6n4, 6n5。其中6n能被6整除合數(shù)。6n2 2(3n1)能被2整除合數(shù)。6n3 3(2n1)能被3整除合數(shù)。6n4 2(3n2)能被2整除合數(shù)。剩下的只有6n1和6n5即6n-1。因此質(zhì)數(shù)除了2和3一定落在這兩種形式中。反之一個(gè)數(shù)如果是6n±1的形式它不一定是質(zhì)數(shù)比如25 6*41但我們可以利用這個(gè)性質(zhì)來(lái)優(yōu)化枚舉我們只需要檢查形如6n±1的數(shù)是否能整除x即可?；谶@個(gè)思想的優(yōu)化版本如下bool is_prime(int x) { if (x 2) return false; if (x 2 || x 3) return true; if (x % 2 0 || x % 3 0) return false; // 排除能被2或3整除的數(shù) // 枚舉形如 6n±1 的數(shù)i, i2 // 從5開(kāi)始56*1-1, 76*11, 116*2-1, 136*21 ... for (int i 5; i x / i; i 6) { // 檢查 i 和 i2 是否能整除 x if (x % i 0 || x % (i 2) 0) return false; } return true; }這個(gè)版本進(jìn)一步減少了需要檢查的除數(shù)數(shù)量。在sqrt(x)范圍內(nèi)我們大約只需要檢查其中1/3的數(shù)因?yàn)槊?個(gè)數(shù)里我們只檢查2個(gè)6n-1和6n1。相比最原始的版本理論上循環(huán)次數(shù)減少了約2/3。實(shí)操心得在算法競(jìng)賽中對(duì)于單次判斷通常使用“跳過(guò)偶數(shù)”的優(yōu)化就足夠了代碼更簡(jiǎn)潔。而在需要反復(fù)調(diào)用、對(duì)性能要求極高的場(chǎng)景例如篩法求質(zhì)數(shù)表中判斷一個(gè)數(shù)是否為質(zhì)數(shù)或者x特別大時(shí)“6n±1”優(yōu)化會(huì)更有價(jià)值。在實(shí)際工程中除非是性能熱點(diǎn)否則代碼的可讀性更重要樸素的i x/i版本往往是首選因?yàn)樗钋逦灰壮鲥e(cuò)。4. 邊界與陷阱代碼實(shí)現(xiàn)中的魔鬼細(xì)節(jié)理論很美好但代碼落地時(shí)魔鬼藏在細(xì)節(jié)里。試除法雖然簡(jiǎn)單但寫(xiě)出健壯、無(wú)懈可擊的代碼需要注意以下幾個(gè)關(guān)鍵點(diǎn)4.1 輸入范圍與數(shù)據(jù)類型題目中x的范圍是[2, 2^31-1]這正是int型正整數(shù)能表示的最大值約21億。這直接影響了我們代碼中的細(xì)節(jié)循環(huán)條件i x / i如前所述這是防止i*i溢出的最佳寫(xiě)法。如果寫(xiě)成i*i x當(dāng)x很大比如接近21億i在幾萬(wàn)量級(jí)時(shí)i*i就可能超過(guò)int范圍導(dǎo)致溢出進(jìn)而引發(fā)未定義行為或錯(cuò)誤判斷。函數(shù)參數(shù)類型雖然題目是int但如果我們想寫(xiě)一個(gè)更通用的函數(shù)考慮x可能更大比如long long范圍那么循環(huán)變量i和條件判斷都需要使用long long類型或者繼續(xù)采用i x / i這種安全的除法形式。4.2 特殊值的處理這是最容易出錯(cuò)的地方。小于2的數(shù)根據(jù)定義質(zhì)數(shù)必須大于1。所以x 2時(shí)要直接返回false。這包括了0,1和所有負(fù)數(shù)。等于2的數(shù)2是最小的質(zhì)數(shù)也是唯一的偶質(zhì)數(shù)。在“跳過(guò)偶數(shù)”的優(yōu)化版本中必須對(duì)x 2進(jìn)行特判否則它會(huì)被if (x % 2 0)排除掉。等于3的數(shù)在“6n±1”優(yōu)化版本中3也需要特判因?yàn)樗环?n±1的形式3 6*03。一個(gè)健壯的實(shí)現(xiàn)必須在優(yōu)化之前先把這些“特殊情況”處理好。4.3 浮點(diǎn)數(shù)陷阱這是一個(gè)經(jīng)典的坑。很多人會(huì)想用sqrt函數(shù)來(lái)獲取上界for (int i 2; i sqrt(x); i) // 不推薦為什么不推薦精度問(wèn)題sqrt返回的是浮點(diǎn)數(shù)。浮點(diǎn)數(shù)計(jì)算和比較可能存在微小的精度誤差。例如理論上sqrt(25)等于5但浮點(diǎn)運(yùn)算結(jié)果可能是4.999999999999999導(dǎo)致i sqrt(x)在i5時(shí)可能不成立從而漏判。性能問(wèn)題在循環(huán)條件中調(diào)用sqrt函數(shù)每次循環(huán)都會(huì)計(jì)算一次平方根除非編譯器做了優(yōu)化這比簡(jiǎn)單的整數(shù)除法x / i開(kāi)銷要大。類型轉(zhuǎn)換需要將int轉(zhuǎn)為double計(jì)算再轉(zhuǎn)回整型比較增加了不必要的開(kāi)銷。因此始終堅(jiān)持使用i x / i作為循環(huán)條件是C/C中實(shí)現(xiàn)試除法的金科玉律。4.4 一個(gè)完整的、魯棒的實(shí)現(xiàn)模板結(jié)合以上所有討論這里給出一個(gè)我個(gè)人在競(jìng)賽和工程中都驗(yàn)證過(guò)無(wú)數(shù)次的“終極”試除法模板。它采用了“跳過(guò)偶數(shù)”的優(yōu)化在簡(jiǎn)潔和效率之間取得了很好的平衡。#include iostream using namespace std; bool is_prime(int x) { // 處理所有特殊情況 if (x 2) return false; // 單獨(dú)處理2和所有偶數(shù) if (x 2) return true; if (x % 2 0) return false; // 只檢查奇數(shù)因子 for (int i 3; i x / i; i 2) { if (x % i 0) return false; } return true; } int main() { int n; cin n; while (n--) { int x; cin x; if (is_prime(x)) puts(Yes); else puts(No); } return 0; }這個(gè)模板的優(yōu)點(diǎn)正確性妥善處理了所有邊界情況負(fù)數(shù)、0、1、2。高效性通過(guò)跳過(guò)偶數(shù)循環(huán)次數(shù)減半。安全性使用i x / i避免溢出。清晰性邏輯層次分明易于理解和維護(hù)。5. 從模板題到實(shí)際應(yīng)用試除法的局限與超越我們通過(guò)AcWing866這道模板題把試除法里里外外剖析了一遍。但作為開(kāi)發(fā)者我們必須清醒地認(rèn)識(shí)到試除法的局限性并知道在什么情況下該尋求更高級(jí)的算法。試除法的局限性時(shí)間復(fù)雜度高O(sqrt(n))。對(duì)于單個(gè)接近10^18的long long型大整數(shù)sqrt(10^18) 10^9這個(gè)計(jì)算量在現(xiàn)代計(jì)算機(jī)上也需要數(shù)秒時(shí)間完全不可接受。僅適用于單點(diǎn)、少量查詢?nèi)绻枰獙?duì)一個(gè)范圍內(nèi)的所有數(shù)進(jìn)行質(zhì)數(shù)判斷或者需要頻繁查詢?cè)嚦ㄐ侍汀３皆嚦ǜ咝У馁|(zhì)數(shù)判定算法當(dāng)問(wèn)題規(guī)模超出試除法的能力范圍時(shí)我們需要更強(qiáng)大的工具M(jìn)iller-Rabin 素性測(cè)試這是一種基于概率的算法。它不能100%確定一個(gè)數(shù)是質(zhì)數(shù)但可以在極短的時(shí)間內(nèi)以極高的概率通常遠(yuǎn)高于硬件出錯(cuò)概率給出正確判斷。它是目前判斷大整數(shù)幾百位甚至上千位是否為質(zhì)數(shù)的實(shí)際標(biāo)準(zhǔn)算法廣泛應(yīng)用于密碼學(xué)如RSA密鑰生成。它的時(shí)間復(fù)雜度是O(k * log^3 n)其中k是測(cè)試輪數(shù)通常取10-20輪就足夠了。埃拉托斯特尼篩法埃氏篩適用于需要獲取一個(gè)區(qū)間如[1, 10^6]內(nèi)所有質(zhì)數(shù)的場(chǎng)景。其核心思想是“標(biāo)記合數(shù)”時(shí)間復(fù)雜度約為O(n log log n)效率遠(yuǎn)高于對(duì)區(qū)間內(nèi)每個(gè)數(shù)單獨(dú)試除。線性篩歐拉篩埃氏篩的優(yōu)化版保證每個(gè)合數(shù)只被其最小質(zhì)因子標(biāo)記一次時(shí)間復(fù)雜度嚴(yán)格為O(n)。是解決區(qū)間質(zhì)數(shù)篩選問(wèn)題的最優(yōu)算法。如何選擇判斷單個(gè)、范圍不大的數(shù)使用優(yōu)化后的試除法本文模板足矣。判斷單個(gè)、非常大的數(shù)10^12使用 Miller-Rabin 算法。需要得到一段區(qū)間內(nèi)所有質(zhì)數(shù)使用埃氏篩或線性篩?；氐轿覀兊腁cWing866題它正是“判斷單個(gè)、范圍不大int范圍內(nèi)”的典型場(chǎng)景因此優(yōu)化試除法是最合適、最直接的工具。掌握它不僅是解決了一道題更是掌握了質(zhì)數(shù)問(wèn)題最基礎(chǔ)的思維模型和代碼實(shí)現(xiàn)技巧為學(xué)習(xí)更復(fù)雜的算法打下了堅(jiān)實(shí)的基礎(chǔ)。下次當(dāng)你再看到質(zhì)數(shù)判斷時(shí)希望你能立刻想起i x / i這個(gè)巧妙的循環(huán)條件以及背后關(guān)于效率與正確性的權(quán)衡。