1. 從一道經典題目說起質因子分解的“基礎”與“不基礎”“1080: 【基礎】質因子”這個標題在很多在線評測平臺OJ和算法競賽的入門題庫里都能看到。乍一看它被歸類為“基礎”題很多剛接觸數論的同學可能會想“不就是把一個數分解成質數相乘嗎這有什么難的” 然而真正上手去寫或者試圖追求一個高效、健壯、能處理各種邊界情況的解法時你會發現這道“基礎”題里藏著不少“不基礎”的細節和技巧。它不僅是理解質數、循環和數學運算的試金石更是通往更高級數論算法如歐拉函數、素數篩法的必經之路。今天我們就來徹底拆解這道題不僅告訴你“怎么做”更要講清楚“為什么這么做”以及在實際編碼和競賽中那些容易踩坑的地方和可以優化的空間。這道題的核心需求非常明確給定一個正整數n要求將其分解質因數并按特定格式輸出。例如輸入120輸出應該是1202*2*2*3*5。格式要求通常是先輸出n然后按質因子從小到大的順序以乘號*連接每個質因子如果同一個質因子出現多次則需要重復輸出。這個看似簡單的輸出格式其實已經隱含了幾個關鍵點分解的順序性、重復因子的處理、以及輸出格式的精確控制。我們將圍繞這些點深入探討從最樸素的試除法到優化方案的完整實現路徑并分享一些在OJ上拿滿分的實戰經驗。2. 質因子分解的核心原理為什么試除法是起點要分解質因子我們首先得理解什么是質數素數一個大于1的自然數如果除了1和它自身外不能被其他自然數整除那么這個數就是質數。而質因子分解就是將一個合數非質數表示為一系列質數相乘的形式并且根據算術基本定理這種表示方式是唯一的不考慮順序。這一定理是我們所有算法的理論基礎。那么如何找到一個數n的質因子呢最直觀、也是最基礎的方法就是試除法。其核心思想非常直接既然最小的質數是2那么我們就從2開始逐個嘗試用質數去整除n。2.1 試除法的基本流程與邏輯試除法的步驟可以清晰地描述如下初始化一個除數i 2。當n 1時循環執行以下操作 a. 判斷i是否能整除n即n % i 0。 b. 如果能整除則i是n的一個質因子。輸出i并將n除以in n / i。 c. 如果不能整除則將i增加1嘗試下一個數。這個邏輯聽起來很簡單但第一個問題就來了為什么從2開始逐個試除就能保證找到的都是質因子比如當i4的時候n可能被4整除嗎如果n能被4整除由于4不是質數我們的算法不就出錯了嗎這里就是理解的關鍵在試除過程中當我們嘗試i4時n已經不可能被4整除了。因為如果n能被4整除意味著它含有因子2^2。而在之前的循環中只要n能被2整除我們就會一直除以2直到n不再包含因子2為止。因此當輪到i4時n已經是一個奇數自然不會被4整除。同理對于任何合數i它的質因子一定小于它本身而這些更小的質因子早已在之前的循環中被從n里“除干凈”了。所以盡管我們循環嘗試了所有整數但真正能整除n的i一定是質數。這是一個非常巧妙且重要的性質它讓我們無需事先判斷i是否為質數大大簡化了代碼。2.2 基礎實現的代碼框架與輸出控制基于以上邏輯我們可以寫出第一版代碼。這里以C為例因為它是算法競賽中最常用的語言之一其思想可以平移到其他語言。#include iostream using namespace std; int main() { int n; cin n; cout n ; // 先輸出 n int i 2; bool isFirst true; // 標記是否是第一個輸出的因子用于控制乘號 while (n 1) { while (n % i 0) { // 內層循環處理同一個質因子的多次出現 if (!isFirst) { cout *; // 不是第一個因子先輸出乘號 } cout i; isFirst false; // 輸出過一個因子后標記為false n / i; // 除掉這個因子 } i; // 嘗試下一個除數 } // 注意這里有一個潛在的巨大漏洞我們稍后會講到。 cout endl; return 0; }這段代碼已經實現了基本功能并且巧妙地使用了一個isFirst布爾變量來控制乘號的輸出避免了末尾多一個乘號的問題。內層的while循環確保了同一個質因子被完全提取例如對于120i2時會循環三次。然而這段代碼隱藏著一個嚴重的性能問題甚至對于某些輸入會導致超時TLE。這就是我們接下來要重點分析和優化的部分。3. 性能瓶頸與核心優化為什么不能試除到 n 本身讓我們思考一下最壞的情況。假設輸入n是一個很大的質數比如n 998244353一個常見的質數。按照上面的算法i會從2開始一直遞增到998244353并且對于每一個i都要執行取模操作n % i直到最后i等于n時才發現它能整除n實際上就是n本身。這意味著循環要進行大約n次時間復雜度是O(n)。對于n在10^9甚至更大的數量級時這樣的算法是完全不可接受的必然超時。那么優化的關鍵在哪里在于一個重要的數學性質如果n是一個合數那么它必定有一個不大于sqrt(n)的質因子。這里sqrt(n)表示n的平方根。我們可以用反證法來理解假設n的所有質因子都大于sqrt(n)。設n a * b且a和b都是大于1的整數。如果a和b都大于sqrt(n)那么a * b sqrt(n) * sqrt(n) n這與a * b n矛盾。因此a和b中至少有一個不大于sqrt(n)。既然a或b的質因子也不大于其本身那么n必然有一個不大于sqrt(n)的質因子。這個性質給我們的算法帶來了革命性的優化我們只需要試除到i * i n即可。因為如果經過所有小于等于sqrt(n)的數的試除后n仍然大于1那么此時剩下的n一定是一個質數并且是原來那個數最大的質因子。原因很簡單如果剩下的n是合數它應該還能被某個小于等于其平方根的因子整除而這個因子必然也小于等于原n的平方根應該在之前的循環中被試除過了這與“剩下的n大于1”矛盾。3.1 優化后的算法流程優化后的算法步驟如下初始化i 2。循環條件改為i * i n。在這個循環里我們專注地找出所有小于等于sqrt(n)的質因子。在循環內部同樣用內層while除盡當前質因子i。循環結束后檢查n是否還大于1。如果是那么此時的n就是最后一個也是最大的質因子。優化后的核心代碼段如下int i 2; bool isFirst true; cout originalN ; // 建議先保存原始輸入值 originalN // 第一段循環試除所有可能小于等于 sqrt(n) 的因子 while (i * i n) { while (n % i 0) { if (!isFirst) cout *; cout i; isFirst false; n / i; } i; } // 第二段處理如果最后剩下的 n 大于1它本身就是一個質因子 if (n 1) { if (!isFirst) cout *; cout n; }經過這個優化算法的時間復雜度從O(n)降到了O(sqrt(n))。對于n 10^12sqrt(n) 10^6循環一百萬次在現代計算機上是完全可以接受的。這是一個質的飛躍。3.2 關于 i 的進一步優化跳過偶數在上面的優化中我們讓i每次遞增1。但仔細想想除了2以外所有的偶數都不可能是質數因為它們能被2整除。因此在試除完2之后我們可以讓i從3開始每次遞增2只檢查奇數。這樣可以減少將近一半的循環次數。// 單獨處理質因子2 while (n % 2 0) { // ... 輸出2并更新n和isFirst n / 2; } // 從3開始每次加2 for (int i 3; i * i n; i 2) { while (n % i 0) { // ... 輸出i并更新n和isFirst n / i; } } if (n 1) { // ... 輸出最后的n }這個優化在常數級別上提升了速度在極端追求性能的場景下可以考慮。但對于入門題目使用i的版本通常已經足夠。4. 邊界條件、特殊輸入與實戰踩坑指南一道題目要想獲得“Accept”不僅要算法正確還要能處理各種邊界情況和滿足嚴格的輸出格式。以下是幾個常見的“坑點”。4.1 輸入為1的情況質因子分解的定義是針對大于1的自然數。1既不是質數也不是合數它沒有質因子。題目通常如何處理輸入1呢我們需要仔細審題。常見的處理方式有兩種題目明確說明輸入范圍n 1。題目未說明但我們需要處理。對于1其輸出格式可能是11或者1無因子。你必須根據題目的具體輸出樣例來決定。如果沒有樣例11是更常見的約定因為這樣能保持n的格式一致性。在我們的代碼中如果輸入1優化后的算法會直接跳過所有循環然后判斷n 1此時n為1條件為假最后什么也不輸出得到1。如果需要輸出11可以在程序開始進行特判int originalN n; cout originalN ; if (originalN 1) { cout 1 endl; return 0; } // ... 后續正常的分解邏輯4.2 輸入為質數的情況當輸入n本身就是一個質數時如17。我們的優化算法會進入while (i*i n)循環但沒有任何i能整除17因為i最大到44*41617。循環結束后n仍然是17大于1于是進入最后的if (n 1)分支輸出17。最終結果是1717這完全正確。這里也體現了我們算法中最后一步if (n 1)的重要性。4.3 輸出格式的精確控制輸出格式是OJ判題系統檢查的重點一個多余的空格或換行都可能導致“Presentation Error”或“Wrong Answer”。乘號連接必須確保在兩個因子之間輸出*且開頭和結尾沒有多余的*。我們使用isFirst標志位的方法是經典且可靠的。換行符大多數OJ要求輸出末尾有換行符endl或\n。先輸出n注意在分解過程中n的值被改變了。所以務必在開始分解前將原始的n保存下來用于輸出。這是一個非常高頻的錯誤。int originalN n; // 保存原始值 cout originalN ; // ... 分解邏輯針對變量 n 進行操作4.4 數據類型的選擇題目給定的n的范圍是多少如果n可能很大比如超過int型的最大值2^31-1約21億那么就需要使用long long類型來存儲n和i。否則在計算i * i時可能會發生溢出導致循環條件判斷錯誤進而引發錯誤或死循環。long long n; cin n; long long i 2; // i 也最好用 long long避免計算 i*i 時溢出 while (i * i n) { // 對于 long long i*i 可能溢出嗎當 i 很大時有可能但通常 i 不會超過 sqrt(LLONG_MAX)在循環結束前是安全的。 // ... }更嚴謹的做法是使用i n / i作為循環條件這完全避免了乘法的溢出風險是競賽中的常用寫法。while (i n / i) { while (n % i 0) { // ... n / i; } i; }5. 從“基礎”到“進階”質因子分解的應用與擴展掌握了質因子分解你就打開了一扇通往數論算法世界的大門。它不僅僅是解決一道OJ題更是許多高級算法和實際問題的基石。5.1 計算正整數的約數個數一個正整數n的約數個數可以通過其質因子分解式快速計算。如果n p1^a1 * p2^a2 * ... * pk^ak其中p1, p2, ..., pk是互不相同的質數那么n的約數總數為(a11) * (a21) * ... * (ak1)。例如120 2^3 * 3^1 * 5^1其約數個數為(31)*(11)*(11) 4*2*216。這個公式在解決與約數、倍數相關的問題時非常有用。5.2 計算歐拉函數 (Euler‘s Totient Function)歐拉函數φ(n)表示小于等于n的正整數中與n互質的數的個數。它的計算也依賴于質因子分解如果n p1^a1 * p2^a2 * ... * pk^ak那么φ(n) n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk)。例如φ(120) 120 * (1-1/2) * (1-1/3) * (1-1/5) 120 * 1/2 * 2/3 * 4/5 32。歐拉函數在RSA加密算法等領域有核心應用。5.3 素數篩法與預處理當我們需要對多個數進行質因子分解或者需要頻繁判斷質數時使用試除法對每個數單獨進行O(sqrt(n))的操作可能效率不足。此時可以預先使用埃拉托斯特尼篩法或線性篩法篩選出一定范圍內比如10^6以內的所有質數并保存到一個數組中。之后進行質因子分解時我們只需要用這個質數數組里的數去試除而不是用所有整數。這樣可以進一步減少不必要的取模運算例如跳過合數4, 6, 8等。// 偽代碼使用預先生成的素數表 prime[] 進行分解 vectorint factors; int temp n; for (int p : primes) { // primes 是預先生成的質數列表 if (p * p temp) break; // 同樣只需要試除到 sqrt(temp) while (temp % p 0) { factors.push_back(p); temp / p; } } if (temp 1) factors.push_back(temp);5.4 在算法競賽中的變形題“質因子”這道題本身可能有很多變種輸出格式變化要求輸出為n 2^3 * 3^1 * 5^1這樣的指數形式。統計質因子種類數只要求輸出有多少個不同的質因子。求最大質因子在分解過程中記錄最大的那個質因子。結合其他數學知識比如求n!階乘的質因子分解這需要用到勒讓德定理。理解基礎的質因子分解算法是應對所有這些變種題目的前提。當你拿到一道新題首先要做的就是將其轉化為你熟悉的基本操作。