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