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