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