因數(shù)分解與約數(shù)生成：從算術(shù)基本定理到高效算法實現(xiàn))
1. 項目概述從“數(shù)數(shù)”到“算數(shù)”的思維躍遷“求一個數(shù)N的正約數(shù)集合”這聽起來像是小學(xué)數(shù)學(xué)課上的練習(xí)題。但如果你曾嘗試過用最樸素的循環(huán)從1到N去逐個判斷當N稍微大一點比如超過10^6程序就會慢得讓你懷疑人生。這恰恰是這個問題最迷人的地方——它表面上是一個簡單的枚舉問題實則是一道絕佳的思維試金石考察的是你能否從“數(shù)數(shù)”的蠻力思維躍遷到“算數(shù)”的分解與組合思維。我在算法競賽和實際開發(fā)中比如設(shè)計哈希表容量、計算資源分配的最優(yōu)粒度無數(shù)次遇到它的變體其核心原理“質(zhì)因數(shù)分解與約數(shù)公式”是數(shù)論中最實用、最優(yōu)雅的工具之一。今天我們就徹底拆解它不僅告訴你“怎么求”更要講透“為什么可以這樣求”以及在不同場景下如何選擇最高效的“武器”。2. 核心原理算術(shù)基本定理與約數(shù)公式理解正約數(shù)的求法絕對不能繞過算術(shù)基本定理。這是整個大廈的地基。2.1 算術(shù)基本定理每個整數(shù)的“基因身份證”任何大于1的整數(shù)N都可以唯一地分解成一系列質(zhì)數(shù)的乘積。這個“唯一”非常關(guān)鍵就像每個人的DNA序列是唯一的一樣。公式表達為N p?^α? × p?^α? × ... × p?^α?其中p?, p?, ..., p? 是互不相同的質(zhì)數(shù)α?, α?, ..., α? 是正整數(shù)。舉個例子360 23 × 32 × 51。這個分解式就是360的“基因身份證”包含了構(gòu)成它的所有基本“元素”質(zhì)數(shù)及其“含量”指數(shù)。2.2 正約數(shù)個數(shù)公式一個排列組合問題既然N由這些質(zhì)因數(shù)冪的乘積構(gòu)成那么N的任何一個正約數(shù)d必然也是由這些相同的質(zhì)因數(shù)構(gòu)成只不過每個質(zhì)因數(shù)的指數(shù)不能超過N中對應(yīng)的指數(shù)。對于質(zhì)因數(shù)p?在約數(shù)d中它的指數(shù)β?可以是多少它可以是0, 1, 2, ..., 一直到α?。也就是說有(α? 1)種選擇。由于各個質(zhì)因數(shù)的選擇是獨立的根據(jù)乘法原理所有可能的組合數(shù)即N的正約數(shù)總個數(shù)τ(N)為τ(N) (α? 1) × (α? 1) × ... × (α? 1)還是以360為例質(zhì)因數(shù)2的指數(shù)是3有 (31)4 種選擇指數(shù)選0,1,2,3。質(zhì)因數(shù)3的指數(shù)是2有 (21)3 種選擇指數(shù)選0,1,2。質(zhì)因數(shù)5的指數(shù)是1有 (11)2 種選擇指數(shù)選0,1。 因此360的正約數(shù)個數(shù) 4 × 3 × 2 24個。注意這個公式計算的是正約數(shù)的個數(shù)。如果要包括負約數(shù)和1以及它自身概念上需要另行處理但在這個正整數(shù)的正約數(shù)語境下我們通常就指這個。2.3 正約數(shù)之和公式延伸理解了個數(shù)公式和公式就順理成章了。它不再是簡單的計數(shù)而是求和。對于每個質(zhì)因數(shù)p?^α?在構(gòu)成約數(shù)時它可以貢獻 p?^0, p?^1, ..., p?^α? 這些不同的“值”。所有可能貢獻的和是一個等比數(shù)列求和p?^0 p?^1 ... p?^α? (p?^(α?1) - 1) / (p? - 1)。同樣根據(jù)獨立性所有約數(shù)的總和σ(N)為σ(N) [(p?^(α?1)-1)/(p?-1)] × [(p?^(α?1)-1)/(p?-1)] × ... × [(p?^(α?1)-1)/(p?-1)]對于360σ(360) [(2?-1)/(2-1)] × [(33-1)/(3-1)] × [(52-1)/(5-1)] (15/1) × (26/2) × (24/4) 15 × 13 × 6 1170。3. 算法實戰(zhàn)如何高效求得所有正約數(shù)知道有多少個約數(shù)只是第一步我們往往需要把它們?nèi)苛谐鰜?。這里根據(jù)不同的需求有不同的策略。3.1 方法一試除法求質(zhì)因數(shù)分解這是所有方法的起點。目標是得到N p?^α? × p?^α? × ... × p?^α?這個形式。def prime_factorization(n): 返回一個列表每個元素為 (質(zhì)因數(shù), 指數(shù)) 的元組 factors [] i 2 # 只需遍歷到 sqrt(n) while i * i n: if n % i 0: cnt 0 while n % i 0: n // i cnt 1 factors.append((i, cnt)) i 1 if i 2 else 2 # 2以后只檢查奇數(shù)小幅優(yōu)化 # 如果最后剩下的n大于1它本身就是一個質(zhì)數(shù) if n 1: factors.append((n, 1)) return factors # 示例分解 360 print(prime_factorization(360)) # 輸出[(2, 3), (3, 2), (5, 1)]原理與細節(jié)為什么到 sqrt(n) 即可如果n有一個大于sqrt(n)的質(zhì)因數(shù)那么它必然與一個小于sqrt(n)的因數(shù)配對。在循環(huán)中通過不斷整除n的值會越來越小。循環(huán)結(jié)束后如果n1那么當前的n就是那個大于sqrt(原始n)的質(zhì)因數(shù)且指數(shù)為1。i的遞增優(yōu)化除了2是偶數(shù)其他質(zhì)數(shù)都是奇數(shù)。所以當i2處理完后可以直接從3開始每次加2跳過所有偶數(shù)這是一個簡單有效的常數(shù)級優(yōu)化。3.2 方法二DFS回溯生成所有約數(shù)得到質(zhì)因數(shù)分解列表factors [(p1, a1), (p2, a2), ...]后生成所有約數(shù)就變成了一個標準的回溯DFS問題每個質(zhì)因數(shù)有(指數(shù)1)種選擇選0次到選α次我們需要遍歷所有組合。def generate_divisors(factors): 根據(jù)質(zhì)因數(shù)分解列表生成所有正約數(shù) divisors [1] # 初始約數(shù)為1 for p, exp in factors: # 遍歷每個質(zhì)因數(shù) current_len len(divisors) # 對于當前已生成的所有約數(shù)分別乘以 p^1, p^2, ..., p^exp for i in range(current_len): val divisors[i] for e in range(1, exp 1): divisors.append(val * (p ** e)) # 更高效的寫法避免重復(fù)計算p的冪 # multiplier 1 # for _ in range(exp): # multiplier * p # for i in range(current_len): # divisors.append(divisors[i] * multiplier) return divisors # 示例生成360的所有約數(shù) factors prime_factorization(360) divisors generate_divisors(factors) divisors.sort() # 排序后輸出 print(f約數(shù)個數(shù){len(divisors)}) print(f約數(shù)列表{divisors}) # 輸出約數(shù)個數(shù)24 # 約數(shù)列表[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360]實操心得這個DFS是隱式的我們通過循環(huán)疊加來實現(xiàn)比遞歸更節(jié)省?？臻g。注意內(nèi)層循環(huán)的邊界current_len len(divisors)一定要在遍歷質(zhì)因數(shù)前獲取。如果在循環(huán)條件里直接寫for i in range(len(divisors))會導(dǎo)致列表在循環(huán)中不斷變長陷入死循環(huán)。排序不是必須的但排序后更便于觀察和后續(xù)使用如查找第k小的約數(shù)。3.3 方法三成對枚舉法僅求集合不依賴分解如果我們不需要質(zhì)因數(shù)分解這個中間結(jié)果只想得到約數(shù)集合并且N不是特別大比如N ≤ 10^12且約數(shù)個數(shù)不會爆炸可以使用更直接的成對枚舉法。def get_divisors_pairwise(n): 通過成對枚舉找出所有約數(shù) divisors_small [] divisors_large [] i 1 while i * i n: # 只遍歷到 sqrt(n) if n % i 0: divisors_small.append(i) # 避免重復(fù)添加平方根 if i ! n // i: divisors_large.append(n // i) i 1 # 將大的約數(shù)列表反轉(zhuǎn)與小的約數(shù)列表拼接得到有序序列 divisors_large.reverse() return divisors_small divisors_large # 示例 print(get_divisors_pairwise(360)) # 輸出[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360]為什么這個方法有效因為約數(shù)總是成對出現(xiàn)的如果d是n的約數(shù)那么n/d也一定是n的約數(shù)。我們只需要枚舉較小的那個約數(shù)d ≤ √n就可以同時得到較大的那個約數(shù)n/d。這個方法的時間復(fù)雜度是 O(√n)在n很大但約數(shù)不多時比先分解再DFS更直觀。重要對比方法二分解DFS和方法三成對枚舉適用場景不同。分解DFS當需要頻繁使用質(zhì)因數(shù)分解結(jié)果時更優(yōu)例如同時需要求約數(shù)個數(shù)、約數(shù)和、歐拉函數(shù)值等。并且當N的質(zhì)因數(shù)分解形式已知或可以預(yù)處理時生成約數(shù)的速度極快。成對枚舉實現(xiàn)簡單邏輯直觀當只需要求一次約數(shù)集合且N不大時很方便。但當N的約數(shù)個數(shù)非常多時例如高度合成數(shù)divisors_large列表反復(fù)插入可能略慢于DFS的列表擴展。4. 性能優(yōu)化與邊界處理在實際編碼中尤其是面對算法競賽或大數(shù)處理時細節(jié)決定成敗。4.1 質(zhì)因數(shù)分解的極致優(yōu)化上面的試除法對于單個查詢已經(jīng)足夠。但對于多組查詢或極大的N10^15我們可以進一步優(yōu)化。預(yù)處理質(zhì)數(shù)表如果需要分解很多個數(shù)可以先用埃拉托斯特尼篩法或歐拉篩預(yù)處理出一定范圍如√N的最大值內(nèi)的所有質(zhì)數(shù)然后用這些質(zhì)數(shù)去試除避免用合數(shù)去試除。Pollard-Rho算法這是一個概率性算法用于分解非常大的整數(shù)通常超過10^18。它的平均時間復(fù)雜度約為O(N^(1/4))但對于編程競賽和一般應(yīng)用掌握試除法及其優(yōu)化已經(jīng)足夠。4.2 大數(shù)約數(shù)個數(shù)溢出的問題約數(shù)個數(shù)公式是連乘增長非常快。一個經(jīng)典的例子是 73513440 2^5 × 3^3 × 5 × 7 × 11 × 13 × 17它的約數(shù)個數(shù)是 (51)(31)(11)^5 642^5 768個。而一些更大的高度合成數(shù)其約數(shù)個數(shù)可以上萬甚至更多。注意事項在計算約數(shù)個數(shù)(α?1)*(α?1)...時中間結(jié)果可能超過32位整型范圍即使在Python中無此擔憂但在C/Java中要使用long long。生成所有約數(shù)列表時如果約數(shù)個數(shù)巨大例如超過10^5內(nèi)存消耗和排序時間O(D log D)D為約數(shù)個數(shù)會成為瓶頸。此時是否真的需要生成全部列表需要根據(jù)業(yè)務(wù)需求慎重考慮。4.3 特殊數(shù)字的處理N11只有一個正約數(shù)就是它本身。質(zhì)因數(shù)分解時1沒有質(zhì)因數(shù)我們的算法循環(huán)會直接跳過最后factors為空列表約數(shù)列表應(yīng)為[1]。需要在生成約數(shù)的函數(shù)開頭做特判。N為質(zhì)數(shù)此時約數(shù)只有1和N。質(zhì)因數(shù)分解結(jié)果為[(N, 1)]約數(shù)個數(shù)為2。N為完全平方數(shù)例如3662。成對枚舉法中當i*i n時i和n//i是同一個數(shù)必須避免重復(fù)添加。這就是代碼中if i ! n // i:判斷的意義。5. 應(yīng)用場景與問題變形理解了原理和算法我們來看看它能解決哪些實際問題。5.1 直接應(yīng)用判斷約數(shù)個數(shù)相關(guān)問題例題1求區(qū)間內(nèi)約數(shù)個數(shù)最多的數(shù)反質(zhì)數(shù)問題給定范圍[L, R]求其中約數(shù)個數(shù)最多的那個數(shù)若有多個輸出最小的。這類問題需要結(jié)合質(zhì)因數(shù)分解和DFS搜索枚舉質(zhì)因數(shù)的指數(shù)組合找到約數(shù)個數(shù)最多且數(shù)值最小的數(shù)。核心就是利用約數(shù)個數(shù)公式進行剪枝搜索。例題2求第k小的約數(shù)給定N和k求N的所有正約數(shù)排序后第k小的那個。思路是先質(zhì)因數(shù)分解然后利用生成約數(shù)的過程但不需要生成全部可以通過計算每個“子樹”下的約數(shù)數(shù)量來指引搜索方向類似于在字典序中查找第k個排列。5.2 間接應(yīng)用其他數(shù)論問題的基石最大公約數(shù)(GCD)與最小公倍數(shù)(LCM)雖然通常用歐幾里得算法但理解其質(zhì)因數(shù)分解形式GCD取指數(shù)最小值LCM取指數(shù)最大值對理解原理至關(guān)重要。歐拉函數(shù)φ(n)計算小于n且與n互質(zhì)的正整數(shù)個數(shù)。公式為 φ(n) n × Π(1 - 1/p?)其中p?是n的質(zhì)因數(shù)。這同樣建立在質(zhì)因數(shù)分解之上。模運算與同余方程在求解 a^x ≡ b (mod n) 這類問題時往往需要分析n的約數(shù)特別是φ(n)的約數(shù)。5.3 實際工程中的影子哈希表容量選擇一個好的哈希表容量通常是一個質(zhì)數(shù)或者至少是一個約數(shù)較少的數(shù)以減少哈希沖突。理解約數(shù)有助于理解為什么選擇這樣的容量。資源分配與分塊當需要將總量為N的資源盡可能均勻地分給m個單元時如果N能被m整除即m是N的約數(shù)那么分配是最均勻的。這在大數(shù)據(jù)分片、并行計算任務(wù)劃分中很常見。計算幾何網(wǎng)格劃分在劃分區(qū)域時若區(qū)域總單元格數(shù)為N希望劃分成大小相等的矩形塊那么塊的個數(shù)必須是N的約數(shù)。6. 常見錯誤與調(diào)試技巧即使理解了原理實現(xiàn)時也難免踩坑。下面是一些常見的“坑點”。6.1 無限循環(huán)或結(jié)果錯誤在生成約數(shù)的循環(huán)中錯誤使用動態(tài)變化的列表長度如前所述for i in range(len(divisors)):在循環(huán)體內(nèi)向divisors添加元素會導(dǎo)致無限循環(huán)。必須用current_len len(divisors)固定循環(huán)次數(shù)。質(zhì)因數(shù)分解中忘記處理最后剩余的n循環(huán)結(jié)束后如果n 1它一定是最后一個質(zhì)因數(shù)。漏掉這步會導(dǎo)致分解不完全進而使約數(shù)個數(shù)和列表都出錯。成對枚舉法的邊界條件循環(huán)條件必須是i * i n而不是i sqrt(n)因為浮點數(shù)運算可能有精度問題。更安全的寫法是i n // i。6.2 性能問題對每個數(shù)都從2開始試除在需要處理多個數(shù)時沒有預(yù)處理質(zhì)數(shù)表導(dǎo)致大量重復(fù)的合數(shù)試除判斷。生成約數(shù)后進行了不必要的全局排序如果業(yè)務(wù)邏輯不要求有序或者可以接受DFS生成的大致有序但不嚴格的列表則可以省去排序的 O(D log D) 時間。用“成對枚舉法”處理約數(shù)極多的數(shù)當N的約數(shù)個數(shù)D很大接近√N量級時成對枚舉法本身的時間復(fù)雜度O(√N)可能遠大于O(D)。例如一個約數(shù)有10萬個的數(shù)其N可能非常大√N的循環(huán)次數(shù)可能遠超10萬。此時如果已知質(zhì)因數(shù)分解用DFS生成O(D)個約數(shù)反而更快。6.3 調(diào)試建議從小數(shù)據(jù)開始用N1, 2, 質(zhì)數(shù)(如17)完全平方數(shù)(如36)以及標準數(shù)(如360)來測試。交叉驗證同時實現(xiàn)“分解DFS”和“成對枚舉”兩種方法對同一個N運行比較結(jié)果是否一致。驗證公式用質(zhì)因數(shù)分解的結(jié)果計算約數(shù)個數(shù)與生成的約數(shù)列表長度對比。打印中間結(jié)果在質(zhì)因數(shù)分解和DFS生成過程中打印出關(guān)鍵的變量如每次找到的質(zhì)因數(shù)、當前的約數(shù)列表有助于快速定位邏輯錯誤。最后我個人的體會是求約數(shù)這個問題是連接數(shù)論基礎(chǔ)與算法實踐的完美橋梁。它教會我們的不僅僅是幾個公式和算法更重要的是一種“分解與組合”的思維模式。在面對一個復(fù)雜問題時先思考能否拆解成獨立的、更簡單的子問題質(zhì)因數(shù)再思考這些子問題的解如何以各種方式組合成最終的解約數(shù)這種化整為零、分而治之的思想在編程和解決工程問題的方方面面都極具價值。下次當你再遇到需要枚舉因子或分解結(jié)構(gòu)的問題時不妨先想想“它的‘質(zhì)因數(shù)’是什么” 質(zhì)因數(shù)分解與約數(shù)生成：從算術(shù)基本定理到高效算法實現(xiàn)
1. 項目概述從“數(shù)數(shù)”到“算數(shù)”的思維躍遷“求一個數(shù)N的正約數(shù)集合”這聽起來像是小學(xué)數(shù)學(xué)課上的練習(xí)題。但如果你曾嘗試過用最樸素的循環(huán)從1到N去逐個判斷當N稍微大一點比如超過10^6程序就會慢得讓你懷疑人生。這恰恰是這個問題最迷人的地方——它表面上是一個簡單的枚舉問題實則是一道絕佳的思維試金石考察的是你能否從“數(shù)數(shù)”的蠻力思維躍遷到“算數(shù)”的分解與組合思維。我在算法競賽和實際開發(fā)中比如設(shè)計哈希表容量、計算資源分配的最優(yōu)粒度無數(shù)次遇到它的變體其核心原理“質(zhì)因數(shù)分解與約數(shù)公式”是數(shù)論中最實用、最優(yōu)雅的工具之一。今天我們就徹底拆解它不僅告訴你“怎么求”更要講透“為什么可以這樣求”以及在不同場景下如何選擇最高效的“武器”。2. 核心原理算術(shù)基本定理與約數(shù)公式理解正約數(shù)的求法絕對不能繞過算術(shù)基本定理。這是整個大廈的地基。2.1 算術(shù)基本定理每個整數(shù)的“基因身份證”任何大于1的整數(shù)N都可以唯一地分解成一系列質(zhì)數(shù)的乘積。這個“唯一”非常關(guān)鍵就像每個人的DNA序列是唯一的一樣。公式表達為N p?^α? × p?^α? × ... × p?^α?其中p?, p?, ..., p? 是互不相同的質(zhì)數(shù)α?, α?, ..., α? 是正整數(shù)。舉個例子360 23 × 32 × 51。這個分解式就是360的“基因身份證”包含了構(gòu)成它的所有基本“元素”質(zhì)數(shù)及其“含量”指數(shù)。2.2 正約數(shù)個數(shù)公式一個排列組合問題既然N由這些質(zhì)因數(shù)冪的乘積構(gòu)成那么N的任何一個正約數(shù)d必然也是由這些相同的質(zhì)因數(shù)構(gòu)成只不過每個質(zhì)因數(shù)的指數(shù)不能超過N中對應(yīng)的指數(shù)。對于質(zhì)因數(shù)p?在約數(shù)d中它的指數(shù)β?可以是多少它可以是0, 1, 2, ..., 一直到α?。也就是說有(α? 1)種選擇。由于各個質(zhì)因數(shù)的選擇是獨立的根據(jù)乘法原理所有可能的組合數(shù)即N的正約數(shù)總個數(shù)τ(N)為τ(N) (α? 1) × (α? 1) × ... × (α? 1)還是以360為例質(zhì)因數(shù)2的指數(shù)是3有 (31)4 種選擇指數(shù)選0,1,2,3。質(zhì)因數(shù)3的指數(shù)是2有 (21)3 種選擇指數(shù)選0,1,2。質(zhì)因數(shù)5的指數(shù)是1有 (11)2 種選擇指數(shù)選0,1。 因此360的正約數(shù)個數(shù) 4 × 3 × 2 24個。注意這個公式計算的是正約數(shù)的個數(shù)。如果要包括負約數(shù)和1以及它自身概念上需要另行處理但在這個正整數(shù)的正約數(shù)語境下我們通常就指這個。2.3 正約數(shù)之和公式延伸理解了個數(shù)公式和公式就順理成章了。它不再是簡單的計數(shù)而是求和。對于每個質(zhì)因數(shù)p?^α?在構(gòu)成約數(shù)時它可以貢獻 p?^0, p?^1, ..., p?^α? 這些不同的“值”。所有可能貢獻的和是一個等比數(shù)列求和p?^0 p?^1 ... p?^α? (p?^(α?1) - 1) / (p? - 1)。同樣根據(jù)獨立性所有約數(shù)的總和σ(N)為σ(N) [(p?^(α?1)-1)/(p?-1)] × [(p?^(α?1)-1)/(p?-1)] × ... × [(p?^(α?1)-1)/(p?-1)]對于360σ(360) [(2?-1)/(2-1)] × [(33-1)/(3-1)] × [(52-1)/(5-1)] (15/1) × (26/2) × (24/4) 15 × 13 × 6 1170。3. 算法實戰(zhàn)如何高效求得所有正約數(shù)知道有多少個約數(shù)只是第一步我們往往需要把它們?nèi)苛谐鰜?。這里根據(jù)不同的需求有不同的策略。3.1 方法一試除法求質(zhì)因數(shù)分解這是所有方法的起點。目標是得到N p?^α? × p?^α? × ... × p?^α?這個形式。def prime_factorization(n): 返回一個列表每個元素為 (質(zhì)因數(shù), 指數(shù)) 的元組 factors [] i 2 # 只需遍歷到 sqrt(n) while i * i n: if n % i 0: cnt 0 while n % i 0: n // i cnt 1 factors.append((i, cnt)) i 1 if i 2 else 2 # 2以后只檢查奇數(shù)小幅優(yōu)化 # 如果最后剩下的n大于1它本身就是一個質(zhì)數(shù) if n 1: factors.append((n, 1)) return factors # 示例分解 360 print(prime_factorization(360)) # 輸出[(2, 3), (3, 2), (5, 1)]原理與細節(jié)為什么到 sqrt(n) 即可如果n有一個大于sqrt(n)的質(zhì)因數(shù)那么它必然與一個小于sqrt(n)的因數(shù)配對。在循環(huán)中通過不斷整除n的值會越來越小。循環(huán)結(jié)束后如果n1那么當前的n就是那個大于sqrt(原始n)的質(zhì)因數(shù)且指數(shù)為1。i的遞增優(yōu)化除了2是偶數(shù)其他質(zhì)數(shù)都是奇數(shù)。所以當i2處理完后可以直接從3開始每次加2跳過所有偶數(shù)這是一個簡單有效的常數(shù)級優(yōu)化。3.2 方法二DFS回溯生成所有約數(shù)得到質(zhì)因數(shù)分解列表factors [(p1, a1), (p2, a2), ...]后生成所有約數(shù)就變成了一個標準的回溯DFS問題每個質(zhì)因數(shù)有(指數(shù)1)種選擇選0次到選α次我們需要遍歷所有組合。def generate_divisors(factors): 根據(jù)質(zhì)因數(shù)分解列表生成所有正約數(shù) divisors [1] # 初始約數(shù)為1 for p, exp in factors: # 遍歷每個質(zhì)因數(shù) current_len len(divisors) # 對于當前已生成的所有約數(shù)分別乘以 p^1, p^2, ..., p^exp for i in range(current_len): val divisors[i] for e in range(1, exp 1): divisors.append(val * (p ** e)) # 更高效的寫法避免重復(fù)計算p的冪 # multiplier 1 # for _ in range(exp): # multiplier * p # for i in range(current_len): # divisors.append(divisors[i] * multiplier) return divisors # 示例生成360的所有約數(shù) factors prime_factorization(360) divisors generate_divisors(factors) divisors.sort() # 排序后輸出 print(f約數(shù)個數(shù){len(divisors)}) print(f約數(shù)列表{divisors}) # 輸出約數(shù)個數(shù)24 # 約數(shù)列表[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360]實操心得這個DFS是隱式的我們通過循環(huán)疊加來實現(xiàn)比遞歸更節(jié)省?？臻g。注意內(nèi)層循環(huán)的邊界current_len len(divisors)一定要在遍歷質(zhì)因數(shù)前獲取。如果在循環(huán)條件里直接寫for i in range(len(divisors))會導(dǎo)致列表在循環(huán)中不斷變長陷入死循環(huán)。排序不是必須的但排序后更便于觀察和后續(xù)使用如查找第k小的約數(shù)。3.3 方法三成對枚舉法僅求集合不依賴分解如果我們不需要質(zhì)因數(shù)分解這個中間結(jié)果只想得到約數(shù)集合并且N不是特別大比如N ≤ 10^12且約數(shù)個數(shù)不會爆炸可以使用更直接的成對枚舉法。def get_divisors_pairwise(n): 通過成對枚舉找出所有約數(shù) divisors_small [] divisors_large [] i 1 while i * i n: # 只遍歷到 sqrt(n) if n % i 0: divisors_small.append(i) # 避免重復(fù)添加平方根 if i ! n // i: divisors_large.append(n // i) i 1 # 將大的約數(shù)列表反轉(zhuǎn)與小的約數(shù)列表拼接得到有序序列 divisors_large.reverse() return divisors_small divisors_large # 示例 print(get_divisors_pairwise(360)) # 輸出[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360]為什么這個方法有效因為約數(shù)總是成對出現(xiàn)的如果d是n的約數(shù)那么n/d也一定是n的約數(shù)。我們只需要枚舉較小的那個約數(shù)d ≤ √n就可以同時得到較大的那個約數(shù)n/d。這個方法的時間復(fù)雜度是 O(√n)在n很大但約數(shù)不多時比先分解再DFS更直觀。重要對比方法二分解DFS和方法三成對枚舉適用場景不同。分解DFS當需要頻繁使用質(zhì)因數(shù)分解結(jié)果時更優(yōu)例如同時需要求約數(shù)個數(shù)、約數(shù)和、歐拉函數(shù)值等。并且當N的質(zhì)因數(shù)分解形式已知或可以預(yù)處理時生成約數(shù)的速度極快。成對枚舉實現(xiàn)簡單邏輯直觀當只需要求一次約數(shù)集合且N不大時很方便。但當N的約數(shù)個數(shù)非常多時例如高度合成數(shù)divisors_large列表反復(fù)插入可能略慢于DFS的列表擴展。4. 性能優(yōu)化與邊界處理在實際編碼中尤其是面對算法競賽或大數(shù)處理時細節(jié)決定成敗。4.1 質(zhì)因數(shù)分解的極致優(yōu)化上面的試除法對于單個查詢已經(jīng)足夠。但對于多組查詢或極大的N10^15我們可以進一步優(yōu)化。預(yù)處理質(zhì)數(shù)表如果需要分解很多個數(shù)可以先用埃拉托斯特尼篩法或歐拉篩預(yù)處理出一定范圍如√N的最大值內(nèi)的所有質(zhì)數(shù)然后用這些質(zhì)數(shù)去試除避免用合數(shù)去試除。Pollard-Rho算法這是一個概率性算法用于分解非常大的整數(shù)通常超過10^18。它的平均時間復(fù)雜度約為O(N^(1/4))但對于編程競賽和一般應(yīng)用掌握試除法及其優(yōu)化已經(jīng)足夠。4.2 大數(shù)約數(shù)個數(shù)溢出的問題約數(shù)個數(shù)公式是連乘增長非常快。一個經(jīng)典的例子是 73513440 2^5 × 3^3 × 5 × 7 × 11 × 13 × 17它的約數(shù)個數(shù)是 (51)(31)(11)^5 642^5 768個。而一些更大的高度合成數(shù)其約數(shù)個數(shù)可以上萬甚至更多。注意事項在計算約數(shù)個數(shù)(α?1)*(α?1)...時中間結(jié)果可能超過32位整型范圍即使在Python中無此擔憂但在C/Java中要使用long long。生成所有約數(shù)列表時如果約數(shù)個數(shù)巨大例如超過10^5內(nèi)存消耗和排序時間O(D log D)D為約數(shù)個數(shù)會成為瓶頸。此時是否真的需要生成全部列表需要根據(jù)業(yè)務(wù)需求慎重考慮。4.3 特殊數(shù)字的處理N11只有一個正約數(shù)就是它本身。質(zhì)因數(shù)分解時1沒有質(zhì)因數(shù)我們的算法循環(huán)會直接跳過最后factors為空列表約數(shù)列表應(yīng)為[1]。需要在生成約數(shù)的函數(shù)開頭做特判。N為質(zhì)數(shù)此時約數(shù)只有1和N。質(zhì)因數(shù)分解結(jié)果為[(N, 1)]約數(shù)個數(shù)為2。N為完全平方數(shù)例如3662。成對枚舉法中當i*i n時i和n//i是同一個數(shù)必須避免重復(fù)添加。這就是代碼中if i ! n // i:判斷的意義。5. 應(yīng)用場景與問題變形理解了原理和算法我們來看看它能解決哪些實際問題。5.1 直接應(yīng)用判斷約數(shù)個數(shù)相關(guān)問題例題1求區(qū)間內(nèi)約數(shù)個數(shù)最多的數(shù)反質(zhì)數(shù)問題給定范圍[L, R]求其中約數(shù)個數(shù)最多的那個數(shù)若有多個輸出最小的。這類問題需要結(jié)合質(zhì)因數(shù)分解和DFS搜索枚舉質(zhì)因數(shù)的指數(shù)組合找到約數(shù)個數(shù)最多且數(shù)值最小的數(shù)。核心就是利用約數(shù)個數(shù)公式進行剪枝搜索。例題2求第k小的約數(shù)給定N和k求N的所有正約數(shù)排序后第k小的那個。思路是先質(zhì)因數(shù)分解然后利用生成約數(shù)的過程但不需要生成全部可以通過計算每個“子樹”下的約數(shù)數(shù)量來指引搜索方向類似于在字典序中查找第k個排列。5.2 間接應(yīng)用其他數(shù)論問題的基石最大公約數(shù)(GCD)與最小公倍數(shù)(LCM)雖然通常用歐幾里得算法但理解其質(zhì)因數(shù)分解形式GCD取指數(shù)最小值LCM取指數(shù)最大值對理解原理至關(guān)重要。歐拉函數(shù)φ(n)計算小于n且與n互質(zhì)的正整數(shù)個數(shù)。公式為 φ(n) n × Π(1 - 1/p?)其中p?是n的質(zhì)因數(shù)。這同樣建立在質(zhì)因數(shù)分解之上。模運算與同余方程在求解 a^x ≡ b (mod n) 這類問題時往往需要分析n的約數(shù)特別是φ(n)的約數(shù)。5.3 實際工程中的影子哈希表容量選擇一個好的哈希表容量通常是一個質(zhì)數(shù)或者至少是一個約數(shù)較少的數(shù)以減少哈希沖突。理解約數(shù)有助于理解為什么選擇這樣的容量。資源分配與分塊當需要將總量為N的資源盡可能均勻地分給m個單元時如果N能被m整除即m是N的約數(shù)那么分配是最均勻的。這在大數(shù)據(jù)分片、并行計算任務(wù)劃分中很常見。計算幾何網(wǎng)格劃分在劃分區(qū)域時若區(qū)域總單元格數(shù)為N希望劃分成大小相等的矩形塊那么塊的個數(shù)必須是N的約數(shù)。6. 常見錯誤與調(diào)試技巧即使理解了原理實現(xiàn)時也難免踩坑。下面是一些常見的“坑點”。6.1 無限循環(huán)或結(jié)果錯誤在生成約數(shù)的循環(huán)中錯誤使用動態(tài)變化的列表長度如前所述for i in range(len(divisors)):在循環(huán)體內(nèi)向divisors添加元素會導(dǎo)致無限循環(huán)。必須用current_len len(divisors)固定循環(huán)次數(shù)。質(zhì)因數(shù)分解中忘記處理最后剩余的n循環(huán)結(jié)束后如果n 1它一定是最后一個質(zhì)因數(shù)。漏掉這步會導(dǎo)致分解不完全進而使約數(shù)個數(shù)和列表都出錯。成對枚舉法的邊界條件循環(huán)條件必須是i * i n而不是i sqrt(n)因為浮點數(shù)運算可能有精度問題。更安全的寫法是i n // i。6.2 性能問題對每個數(shù)都從2開始試除在需要處理多個數(shù)時沒有預(yù)處理質(zhì)數(shù)表導(dǎo)致大量重復(fù)的合數(shù)試除判斷。生成約數(shù)后進行了不必要的全局排序如果業(yè)務(wù)邏輯不要求有序或者可以接受DFS生成的大致有序但不嚴格的列表則可以省去排序的 O(D log D) 時間。用“成對枚舉法”處理約數(shù)極多的數(shù)當N的約數(shù)個數(shù)D很大接近√N量級時成對枚舉法本身的時間復(fù)雜度O(√N)可能遠大于O(D)。例如一個約數(shù)有10萬個的數(shù)其N可能非常大√N的循環(huán)次數(shù)可能遠超10萬。此時如果已知質(zhì)因數(shù)分解用DFS生成O(D)個約數(shù)反而更快。6.3 調(diào)試建議從小數(shù)據(jù)開始用N1, 2, 質(zhì)數(shù)(如17)完全平方數(shù)(如36)以及標準數(shù)(如360)來測試。交叉驗證同時實現(xiàn)“分解DFS”和“成對枚舉”兩種方法對同一個N運行比較結(jié)果是否一致。驗證公式用質(zhì)因數(shù)分解的結(jié)果計算約數(shù)個數(shù)與生成的約數(shù)列表長度對比。打印中間結(jié)果在質(zhì)因數(shù)分解和DFS生成過程中打印出關(guān)鍵的變量如每次找到的質(zhì)因數(shù)、當前的約數(shù)列表有助于快速定位邏輯錯誤。最后我個人的體會是求約數(shù)這個問題是連接數(shù)論基礎(chǔ)與算法實踐的完美橋梁。它教會我們的不僅僅是幾個公式和算法更重要的是一種“分解與組合”的思維模式。在面對一個復(fù)雜問題時先思考能否拆解成獨立的、更簡單的子問題質(zhì)因數(shù)再思考這些子問題的解如何以各種方式組合成最終的解約數(shù)這種化整為零、分而治之的思想在編程和解決工程問題的方方面面都極具價值。下次當你再遇到需要枚舉因子或分解結(jié)構(gòu)的問題時不妨先想想“它的‘質(zhì)因數(shù)’是什么”