1. 從一道面試題說起為什么分解質(zhì)因數(shù)這么重要前幾天幫一個(gè)學(xué)弟復(fù)盤面試他掛在了二面的一道基礎(chǔ)算法題上。題目很簡單給定一個(gè)正整數(shù) N請(qǐng)輸出它的所有質(zhì)因數(shù)及其對(duì)應(yīng)的指數(shù)。比如輸入 12輸出2^2 * 3^1。學(xué)弟當(dāng)時(shí)用了最樸素的思路——從 2 遍歷到 N判斷每個(gè)數(shù)是否能整除 N如果是質(zhì)數(shù)就記錄。結(jié)果當(dāng) N 接近 10^9 時(shí)程序直接超時(shí)。面試官追問優(yōu)化思路他卡殼了。這其實(shí)暴露了一個(gè)很典型的問題很多初學(xué)者對(duì)“分解質(zhì)因數(shù)”的理解還停留在小學(xué)數(shù)學(xué)的概念層面沒有將其轉(zhuǎn)化為高效的算法思維。而在算法競賽如 AcWing、LeetCode和實(shí)際開發(fā)如 RSA 加密原理、哈希沖突處理中質(zhì)因數(shù)分解是理解數(shù)論、設(shè)計(jì)高效算法的基石。AcWing 算法基礎(chǔ)課將其作為數(shù)論部分的核心內(nèi)容正是因?yàn)樗猩蠁⑾率抢斫夂罄m(xù)歐拉函數(shù)、約數(shù)個(gè)數(shù)等知識(shí)的關(guān)鍵。試除法作為分解質(zhì)因數(shù)最直觀、最基礎(chǔ)的算法其價(jià)值不在于處理極大的數(shù)字那是 Pollard Rho 算法的領(lǐng)域而在于它完美地體現(xiàn)了“用計(jì)算機(jī)思維解決數(shù)學(xué)問題”的過程。通過它我們能深刻理解時(shí)間復(fù)雜度分析、循環(huán)邊界優(yōu)化、以及如何利用數(shù)學(xué)性質(zhì)如“一個(gè)合數(shù)必有一個(gè)不大于其平方根的質(zhì)因數(shù)”來大幅提升效率。今天我們就拋開教科書的刻板描述從實(shí)戰(zhàn)和原理出發(fā)把試除法分解質(zhì)因數(shù)這件事掰開揉碎了講清楚。2. 試除法的核心原理不只是“除”那么簡單試除法的思想非常直接對(duì)于一個(gè)正整數(shù)n我們從小到大枚舉所有可能的質(zhì)因數(shù)i如果能整除就不斷地除以i直到不能整除為止同時(shí)記錄除的次數(shù)即指數(shù)。枚舉完如果n還大于 1那么剩下的n本身就是一個(gè)質(zhì)數(shù)。這個(gè)描述聽起來平平無奇但其中蘊(yùn)含了兩個(gè)至關(guān)重要的優(yōu)化點(diǎn)也是面試和筆試中區(qū)分“背答案”和“真理解”的關(guān)鍵。2.1 優(yōu)化一枚舉到 sqrt(n) 就夠了嗎這是最廣為人知的優(yōu)化。原理是如果n是一個(gè)合數(shù)那么它必定有一個(gè)不大于sqrt(n)的質(zhì)因子。這個(gè)結(jié)論是試除法效率的基石。為什么我們可以用反證法來理解。假設(shè)n的所有質(zhì)因子都大于sqrt(n)。設(shè)最小的質(zhì)因子為p那么p sqrt(n)。因?yàn)閚是合數(shù)至少還有一個(gè)因子q n / p。由于p是最小的所以q p sqrt(n)。那么p * q sqrt(n) * sqrt(n) n這與p * q n矛盾。因此假設(shè)不成立n必有一個(gè)不大于sqrt(n)的質(zhì)因子。在代碼中這意味著我們的for循環(huán)條件可以寫成i n / i等價(jià)于i * i n但能防止i*i溢出。這個(gè)小小的改動(dòng)能將時(shí)間復(fù)雜度從 O(n) 降為 O(sqrt(n))對(duì)于n10^9的情況遍歷次數(shù)從十億級(jí)降到了三萬級(jí)這是質(zhì)的飛躍。注意這里有一個(gè)新手極易混淆的點(diǎn)。循環(huán)條件是i n / i但循環(huán)體內(nèi)的n是動(dòng)態(tài)變化的每次除盡質(zhì)因子后n會(huì)變小。這個(gè)條件依然正確嗎正確。因?yàn)楫?dāng)我們枚舉到i時(shí)n中所有小于i的質(zhì)因子都已經(jīng)被除干凈了。如果當(dāng)前i能整除n那么i必然是質(zhì)數(shù)證明如果i是合數(shù)那么它的質(zhì)因子小于i而這些小于i的質(zhì)因子已經(jīng)在之前被枚舉并除盡了矛盾。因此我們始終在枚舉質(zhì)因子而n的剩余部分其最小質(zhì)因子一定大于等于當(dāng)前的i。所以當(dāng)i大于sqrt(當(dāng)前n)時(shí)當(dāng)前n要么是 1要么是一個(gè)質(zhì)數(shù)。循環(huán)結(jié)束后對(duì)n 1的處理正是為了收集這個(gè)最后的質(zhì)因子。2.2 優(yōu)化二為什么可以放心地每次i這是第二個(gè)精妙之處。我們并沒有在循環(huán)里判斷i是否為質(zhì)數(shù)而是直接判斷n % i 0。如果i是合數(shù)它可能整除n嗎答案是不可能。原因接續(xù)上面的邏輯當(dāng)代碼執(zhí)行到i時(shí)n中所有小于i的質(zhì)因子已經(jīng)被除盡。如果i是合數(shù)設(shè)其某個(gè)質(zhì)因子為pp i。因?yàn)閜是i的因子如果i能整除n那么p也一定能整除n。但這與“n中所有小于i的質(zhì)因子已被除盡”矛盾因?yàn)閜小于i且是質(zhì)數(shù)。因此凡是能進(jìn)入if (n % i 0)分支的i一定是質(zhì)數(shù)。這個(gè)特性省去了每次判斷i是否為質(zhì)數(shù)的開銷讓代碼極其簡潔高效。它依賴于算法步驟本身帶來的“過濾”效果是理解試除法邏輯閉環(huán)的關(guān)鍵。3. 手把手實(shí)現(xiàn)代碼逐行解析與避坑指南理解了原理我們來看 C 的標(biāo)準(zhǔn)實(shí)現(xiàn)。我會(huì)逐行分析并指出幾個(gè)常見的“坑”。void divide(int n) { // 遍歷所有可能的小于等于sqrt(n)的質(zhì)因子 for (int i 2; i n / i; i) { // 如果i能整除n那么i一定是n的質(zhì)因子 if (n % i 0) { int s 0; // 指數(shù)計(jì)數(shù)器 // 將n中所有因子i除盡 while (n % i 0) { n / i; s; } // 輸出質(zhì)因子i及其指數(shù)s printf(%d %d\n, i, s); } } // 處理可能剩余的那個(gè)大于sqrt(原始n)的質(zhì)因子 if (n 1) { printf(%d %d\n, n, 1); } }逐行解讀與避坑點(diǎn)循環(huán)條件i n / i這是防止整數(shù)溢出的最佳寫法。寫成i * i n在i較大時(shí)可能導(dǎo)致i*i溢出。寫成i sqrt(n)則需要每次循環(huán)計(jì)算sqrt有精度和性能開銷。i n / i是最優(yōu)選擇。if (n % i 0)的判斷如前所述走到這里的i一定是質(zhì)數(shù)。這是算法的“魔法”所在無需額外判斷。while (n % i 0)循環(huán)這個(gè)循環(huán)有兩個(gè)作用。一是精確計(jì)算質(zhì)因子i的指數(shù)s二是在計(jì)算過程中不斷減小n這直接影響了外層for循環(huán)的終止條件i n / i使得算法能提前結(jié)束。這是動(dòng)態(tài)邊界帶來的額外效率提升。最后的if (n 1)這是整個(gè)算法的收尾關(guān)鍵也是最容易被遺忘的一步。經(jīng)過循環(huán)后n的值可能變?yōu)?1說明所有質(zhì)因子都已找到也可能是一個(gè)大于 1 的數(shù)。根據(jù)優(yōu)化一的原理這個(gè)大于 1 的n一定是原始n的一個(gè)質(zhì)因子并且它大于原始n的平方根。例如n 13質(zhì)數(shù)循環(huán)不會(huì)進(jìn)入因?yàn)? 13/2最后n13 1輸出13 1。再如n 22循環(huán)會(huì)找到質(zhì)因子 2除盡后n變?yōu)?11此時(shí)i33 11/3循環(huán)結(jié)束剩余的n11就是另一個(gè)質(zhì)因子。一個(gè)經(jīng)典的調(diào)試案例假設(shè)輸入n 12。i2滿足2 12/2進(jìn)入循環(huán)。12 % 2 0成立進(jìn)入內(nèi)層whilen依次變?yōu)?6, 3s2。輸出2 2。i3此時(shí)n3滿足3 3/3即3 1不成立。注意這里循環(huán)條件i n / i變成了3 3/3 1為假所以外層for循環(huán)結(jié)束。執(zhí)行最后的if (n 1)此時(shí)n3輸出3 1。 結(jié)果正確12 2^2 * 3^1。這個(gè)例子清晰地展示了動(dòng)態(tài)n如何使循環(huán)提前終止。4. 時(shí)間復(fù)雜度分析與不同場景下的表現(xiàn)我們常說試除法分解質(zhì)因數(shù)的時(shí)間復(fù)雜度是 O(sqrt(n))。這個(gè)說法需要細(xì)化因?yàn)樗枋龅氖亲顗那闆r。最壞情況當(dāng)n本身是一個(gè)質(zhì)數(shù)時(shí)我們需要遍歷i從 2 到sqrt(n)才能確認(rèn)時(shí)間復(fù)雜度為 O(sqrt(n))。最好情況當(dāng)n是 2 的冪如n2^k時(shí)第一次循環(huán)i2就會(huì)進(jìn)入while將n除到 1循環(huán)提前結(jié)束時(shí)間復(fù)雜度接近 O(log n)。平均情況復(fù)雜度低于 O(sqrt(n))因?yàn)閚會(huì)在除盡小因子后迅速變小縮短了循環(huán)次數(shù)。但對(duì)于算法分析我們通常用最壞復(fù)雜度來評(píng)估其性能上限。在實(shí)際應(yīng)用和算法題中這個(gè)復(fù)雜度意味著對(duì)于n 10^7的情況試除法游刃有余。對(duì)于n 10^9的情況sqrt(10^9) ≈ 31622三萬多次循環(huán)在現(xiàn)代計(jì)算機(jī)上也是瞬間完成完全可行。對(duì)于n 10^12或更大試除法就會(huì)開始吃力百萬次循環(huán)這時(shí)就需要更高級(jí)的算法如 Pollard Rho時(shí)間復(fù)雜度期望為 O(n^{1/4})。這里分享一個(gè)我踩過的坑在一次線上比賽中題目需要對(duì)多個(gè)數(shù)進(jìn)行質(zhì)因數(shù)分解我直接對(duì)每個(gè)數(shù)調(diào)用divide函數(shù)。當(dāng)查詢次數(shù)Q很大如Q10^5且每個(gè)數(shù)n都接近10^9時(shí)總計(jì)算量Q * sqrt(n)就會(huì)超時(shí)。正確的優(yōu)化思路是預(yù)處理先用線性篩法求出一定范圍內(nèi)如sqrt(最大n)的所有質(zhì)數(shù)存儲(chǔ)在數(shù)組中。然后在divide函數(shù)中不再用i枚舉所有數(shù)而是直接枚舉預(yù)處理好的質(zhì)數(shù)數(shù)組。這樣內(nèi)層循環(huán)次數(shù)從sqrt(n)降為了sqrt(n) / log(sqrt(n))對(duì)于大量查詢的場景性能提升顯著。5. 不止于分解質(zhì)因數(shù)分解的典型應(yīng)用場景理解了算法更要明白用它來做什么。質(zhì)因數(shù)分解絕不是一道孤立的算法題它是解決許多復(fù)雜問題的“瑞士軍刀”。5.1 計(jì)算正整數(shù)的約數(shù)個(gè)數(shù)與約數(shù)之和這是最直接的應(yīng)用。根據(jù)數(shù)論定理如果一個(gè)數(shù)N質(zhì)因數(shù)分解為N p1^a1 * p2^a2 * ... * pk^ak。那么它的約數(shù)個(gè)數(shù)為(a11) * (a21) * ... * (ak1)。每個(gè)質(zhì)因子可以取 0 到 ai 次冪相乘得到所有組合它的約數(shù)之和為(p1^0 p1^1 ... p1^a1) * ... * (pk^0 ... pk^ak)。利用試除法得到pi和ai后這兩個(gè)值可以輕松算出。很多題目會(huì)偽裝成“求約數(shù)個(gè)數(shù)”本質(zhì)就是考質(zhì)因數(shù)分解。5.2 判斷兩個(gè)數(shù)是否互質(zhì)如果兩個(gè)數(shù)a和b的最大公約數(shù)gcd(a, b) 1則它們互質(zhì)。一種方法是用歐幾里得算法求gcd。另一種思路是分別分解a和b的質(zhì)因數(shù)如果它們沒有公共的質(zhì)因子則互質(zhì)。雖然效率不如gcd但這種思路在需要同時(shí)獲取質(zhì)因數(shù)信息的場景下很有用。5.3 簡化分?jǐn)?shù)或比例問題例如題目要求將分?jǐn)?shù)a/b化為最簡形式。我們需要找到分子分母的最大公約數(shù)g然后同時(shí)除以g。如何找g可以對(duì)a和b分別分解質(zhì)因數(shù)找出所有公共質(zhì)因子的最低次冪乘積就是g。這同樣是歐幾里得算法的替代思路在某些特定場景下如需要記錄化簡過程更直觀。5.4 解決模運(yùn)算與同余方程在初等數(shù)論中解一些同余方程時(shí)常常需要將模數(shù)m分解質(zhì)因數(shù)然后轉(zhuǎn)化為若干個(gè)模p^kp是質(zhì)數(shù)的方程再用中國剩余定理組合解。這是 RSA 等加密算法背后的數(shù)學(xué)原理之一。實(shí)戰(zhàn)心得不要死記硬背應(yīng)用場景。最好的方法是每當(dāng)你看到一個(gè)算法都問自己“這個(gè)算法的輸出結(jié)果質(zhì)因數(shù)列表能用來計(jì)算什么” 把質(zhì)因數(shù)分解看作一個(gè)信息提取工具它把整數(shù)n壓縮成了一組(質(zhì)數(shù), 指數(shù))的鍵值對(duì)。后續(xù)幾乎所有關(guān)于n的算術(shù)性質(zhì)問題都可以通過操作這組鍵值對(duì)來高效解決。這種“降維”思維才是學(xué)習(xí)算法的核心。6. 從試除法出發(fā)算法思想的延伸與對(duì)比試除法是“暴力枚舉”思想在數(shù)論領(lǐng)域的經(jīng)典體現(xiàn)。通過它我們可以延伸到其他重要的算法思想。與判斷質(zhì)數(shù)的試除法對(duì)比判斷單個(gè)數(shù)n是否為質(zhì)數(shù)也可以用類似的循環(huán)for (int i2; in/i; i)。但注意那里沒有內(nèi)層的while循環(huán)因?yàn)槟康闹皇桥袛嗍欠翊嬖谝粋€(gè)因子找到任何一個(gè)就可以立即返回false。而分解質(zhì)因數(shù)要求找出所有因子所以需要while除盡。兩者代碼相似但目的和細(xì)節(jié)的差異恰恰是面試官喜歡考察的點(diǎn)。向更高效算法的演進(jìn)當(dāng)n很大時(shí)試除法O(sqrt(n))的復(fù)雜度不夠用。于是有了Miller-Rabin 素性測試一個(gè)基于概率的快速判斷大數(shù)是否為質(zhì)數(shù)的算法。Pollard Rho 因數(shù)分解算法一個(gè)用于分解大整數(shù)的隨機(jī)算法期望時(shí)間復(fù)雜度為O(n^{1/4})。它的核心思想之一是“隨機(jī)漫步”和“生日悖論”與試除法的確定性枚舉截然不同。學(xué)習(xí)試除法是理解這些高級(jí)算法為何必要、以及它們優(yōu)化了什么的基石。在 AcWing 課程體系中的位置在 AcWing 算法基礎(chǔ)課的數(shù)論章節(jié)試除法分解質(zhì)因數(shù)通常緊接在“試除法判斷質(zhì)數(shù)”之后位于“篩質(zhì)數(shù)”埃氏篩、線性篩之前。這個(gè)安排非常合理它先用小規(guī)模問題單個(gè)數(shù)引入枚舉和優(yōu)化思想然后過渡到需要獲取完整質(zhì)因數(shù)信息的“分解”問題最后再推廣到需要一次性處理大量數(shù)的“篩選”問題。層層遞進(jìn)由點(diǎn)及面。我個(gè)人的學(xué)習(xí)建議是在學(xué)完試除法后一定要手動(dòng)模擬分解幾個(gè)典型數(shù)字比如 24, 56, 97, 1001。在紙上一步步走完循環(huán)觀察n和i的變化。這個(gè)過程能極大地強(qiáng)化你對(duì)“動(dòng)態(tài)邊界”和“最后剩余質(zhì)因子”這兩個(gè)關(guān)鍵點(diǎn)的理解。很多邏輯上的疑惑在紙筆模擬面前都會(huì)煙消云散。最后雖然現(xiàn)在有很多模板代碼可以直接套用但我強(qiáng)烈建議在初學(xué)階段自己從頭實(shí)現(xiàn)幾遍。從最樸素的O(n)版本開始逐步加入sqrt(n)優(yōu)化最后寫出帶n1處理的完整版。這個(gè)迭代過程能讓你真正內(nèi)化算法的每一個(gè)優(yōu)化步驟明白其所以然。當(dāng)你再遇到類似“枚舉優(yōu)化”的問題時(shí)這種思維模式會(huì)自然而然地浮現(xiàn)出來這才是刷算法題最重要的收獲。