1. 項目概述一道關(guān)于質(zhì)數(shù)篩選與區(qū)間計數(shù)的算法題最近在整理一些算法競賽的題目翻到了這道來自JZOJ一個知名的在線評測系統(tǒng)的題目“prime”。題目本身沒有提供具體的描述但從標(biāo)題和常見的算法競賽語境來看這大概率是一道與質(zhì)數(shù)Prime Number相關(guān)的數(shù)學(xué)或編程問題。結(jié)合“提高組模擬”這個標(biāo)簽可以推斷其難度不低通常會考察參賽者對數(shù)論知識的掌握以及將數(shù)學(xué)思維轉(zhuǎn)化為高效代碼的能力。這類題目在信息學(xué)奧賽OI和各類算法競賽中非常常見核心往往圍繞著質(zhì)數(shù)的判定、篩選、性質(zhì)應(yīng)用以及區(qū)間內(nèi)的計數(shù)問題展開。對于有一定算法基礎(chǔ)的開發(fā)者或?qū)W生來說深入理解這類問題的解法不僅能幫助你在比賽中得分更能鍛煉你處理大規(guī)模數(shù)據(jù)、優(yōu)化時間復(fù)雜度的核心編程能力。今天我就結(jié)合常見的出題套路和“prime”這個關(guān)鍵詞來詳細(xì)拆解一下這類題目的典型解法、核心思路以及在實際編碼中容易踩到的“坑”。2. 質(zhì)數(shù)相關(guān)算法題的常見考點與核心模型雖然我們不知道“JZOJ6825”這道題的具體內(nèi)容但“prime”這個詞已經(jīng)將范圍鎖定得非常明確。在算法競賽中以“prime”為名的題目其考察點通常不會脫離以下幾個經(jīng)典模型。理解這些模型就等于掌握了解決此類問題的鑰匙。2.1 質(zhì)數(shù)判定與埃拉托斯特尼篩法這是所有質(zhì)數(shù)問題的基礎(chǔ)。單點判定一個數(shù)n是否為質(zhì)數(shù)通常采用試除法時間復(fù)雜度為O(√n)。但當(dāng)題目需要處理大量數(shù)字或者需要一個區(qū)間內(nèi)所有質(zhì)數(shù)時篩法就成為了唯一的選擇。最經(jīng)典的是埃拉托斯特尼篩法簡稱埃氏篩。其原理非常直觀從2開始將每個質(zhì)數(shù)的所有倍數(shù)標(biāo)記為合數(shù)。一個常見的優(yōu)化是對于當(dāng)前質(zhì)數(shù)p可以從p*p開始標(biāo)記因為更小的倍數(shù)如2p, 3p, ...已經(jīng)被更小的質(zhì)數(shù)標(biāo)記過了。// 埃氏篩基礎(chǔ)實現(xiàn)標(biāo)記1~n范圍內(nèi)的質(zhì)數(shù) vectorbool is_prime(n1, true); is_prime[0] is_prime[1] false; for (int i 2; i * i n; i) { if (is_prime[i]) { // 從i*i開始標(biāo)記步長為i for (int j i * i; j n; j i) { is_prime[j] false; } } }然而埃氏篩有一個明顯的缺點一個合數(shù)可能會被多個質(zhì)數(shù)重復(fù)標(biāo)記例如6會被2和3都標(biāo)記一次。這在數(shù)據(jù)規(guī)模極大例如n在10^7以上時會帶來不必要的開銷。2.2 線性篩歐拉篩與質(zhì)因數(shù)分解為了解決重復(fù)標(biāo)記的問題線性篩歐拉篩應(yīng)運而生。它的核心思想是讓每個合數(shù)只被其最小的質(zhì)因數(shù)篩掉從而將時間復(fù)雜度嚴(yán)格降到O(n)。這是處理大規(guī)模質(zhì)數(shù)篩選問題的首選算法也是很多復(fù)雜數(shù)論問題的基礎(chǔ)組件。// 線性篩歐拉篩實現(xiàn) vectorint primes; // 保存所有篩出來的質(zhì)數(shù) vectorbool is_prime(n1, true); is_prime[0] is_prime[1] false; for (int i 2; i n; i) { if (is_prime[i]) { primes.push_back(i); } for (int j 0; j primes.size() i * primes[j] n; j) { is_prime[i * primes[j]] false; // 關(guān)鍵保證每個合數(shù)只被最小質(zhì)因子篩掉 if (i % primes[j] 0) { break; } } }與篩法緊密相關(guān)的另一個考點是質(zhì)因數(shù)分解。給定一個數(shù)快速得到其所有質(zhì)因數(shù)及其指數(shù)。結(jié)合線性篩我們可以預(yù)處理出每個數(shù)的最小質(zhì)因數(shù)LPF從而在O(log n)的時間內(nèi)完成對任意數(shù)的分解。這在解決與因子、倍數(shù)、GCD/LCM相關(guān)的問題時至關(guān)重要。2.3 區(qū)間質(zhì)數(shù)統(tǒng)計與二次篩法這是“prime”類題目一個非常熱門的進(jìn)階考點。問題通常描述為給定一個區(qū)間[L, R]其中L和R可能非常大例如1 ≤ L ≤ R ≤ 10^12但R-L ≤ 10^6統(tǒng)計該區(qū)間內(nèi)質(zhì)數(shù)的個數(shù)。顯然我們無法直接用篩法篩到10^12。這時就需要用到區(qū)間篩法或稱二次篩法。其思路非常巧妙先用線性篩預(yù)處理出所有小于等于√R的質(zhì)數(shù)。因為如果區(qū)間內(nèi)的一個數(shù)是合數(shù)它必然有一個不大于其平方根的質(zhì)因子而這個質(zhì)因子一定在我們預(yù)處理出的質(zhì)數(shù)集合中。創(chuàng)建一個長度為R-L1的布爾數(shù)組初始化所有位置為true假設(shè)都是質(zhì)數(shù)。對于每一個預(yù)處理出的質(zhì)數(shù)p找到在區(qū)間[L, R]內(nèi)第一個能被p整除的數(shù)可能需要一點計算然后從這個數(shù)開始將步長為p的所有位置標(biāo)記為false合數(shù)。遍歷最終的布爾數(shù)組統(tǒng)計true的個數(shù)即為區(qū)間內(nèi)質(zhì)數(shù)的數(shù)量。這個模型幾乎可以覆蓋所有“求大區(qū)間內(nèi)質(zhì)數(shù)個數(shù)”的題目。解題的關(guān)鍵在于高效計算每個質(zhì)數(shù)p在區(qū)間內(nèi)的起始位置并注意處理邊界情況比如p本身在區(qū)間內(nèi)時它自己不應(yīng)該被標(biāo)記為合數(shù)。3. 從“prime”出發(fā)的典型題目變形與綜合應(yīng)用單純的質(zhì)數(shù)判定或計數(shù)可能只是題目的第一步。更常見的“提高組”難度題目會將質(zhì)數(shù)作為基礎(chǔ)元素與其他算法或數(shù)學(xué)概念結(jié)合構(gòu)造出更復(fù)雜的問題。以下是我根據(jù)經(jīng)驗總結(jié)的幾種高頻變形。3.1 結(jié)合前綴和的質(zhì)數(shù)貢獻(xiàn)問題題目可能問在區(qū)間[L, R]內(nèi)所有質(zhì)數(shù)的和是多少或者所有質(zhì)數(shù)的某種函數(shù)值如歐拉函數(shù)值之和是多少 這類問題的標(biāo)準(zhǔn)解法是“預(yù)處理前綴和”。我們先通過篩法得到一定范圍內(nèi)通常是題目給出的R的最大值所有質(zhì)數(shù)并計算其貢獻(xiàn)值就是它本身或者是它的函數(shù)值然后生成一個前綴和數(shù)組pre[i]表示從1到i所有質(zhì)數(shù)貢獻(xiàn)值的和。 那么對于任意查詢[L, R]答案就是pre[R] - pre[L-1]。這種“離線預(yù)處理在線O(1)查詢”的思路是處理大量區(qū)間查詢問題的金科玉律。3.2 質(zhì)數(shù)與位運算、字符串的結(jié)合這是一種比較“燒腦”的變形。例如題目可能定義一種“質(zhì)數(shù)權(quán)重”將一個數(shù)的二進(jìn)制表示中1的個數(shù)即popcount作為一個屬性然后問在區(qū)間內(nèi)有多少個數(shù)的popcount值是質(zhì)數(shù)。這里質(zhì)數(shù)扮演了一個“過濾器”或“分類器”的角色。 解題需要分兩步預(yù)處理出一定范圍內(nèi)比如小于等于64因為一個long long類型的數(shù)最多64位的所有質(zhì)數(shù)用于判斷popcount是否為質(zhì)數(shù)。使用數(shù)位DP數(shù)位動態(tài)規(guī)劃來統(tǒng)計區(qū)間[L, R]內(nèi)滿足“二進(jìn)制中1的個數(shù)是質(zhì)數(shù)”這一條件的數(shù)字有多少個。數(shù)位DP是處理此類“數(shù)字各位屬性滿足某種條件”的計數(shù)問題的強(qiáng)大工具。3.3 基于質(zhì)因數(shù)分解的結(jié)構(gòu)性問題這是難度最高的一類。題目可能給出一個與“質(zhì)數(shù)指數(shù)”或“質(zhì)因數(shù)種類數(shù)”相關(guān)的定義然后要求計數(shù)或求最值。例如一個虛構(gòu)但很典型的例子定義一個數(shù)的“質(zhì)數(shù)冪次”為將其進(jìn)行質(zhì)因數(shù)分解后所有指數(shù)之和。求區(qū)間[L, R]內(nèi)“質(zhì)數(shù)冪次”最大的數(shù)。 解決這類問題區(qū)間篩法依然是起點。在區(qū)間篩的過程中我們不僅可以標(biāo)記合數(shù)還可以順便記錄每個數(shù)被哪些質(zhì)數(shù)整除。通過一些額外的數(shù)據(jù)結(jié)構(gòu)如數(shù)組記錄當(dāng)前數(shù)的乘積或指數(shù)信息我們可以在篩的同時完成質(zhì)因數(shù)分解的“預(yù)處理”。之后對區(qū)間內(nèi)每個未被標(biāo)記為合數(shù)的數(shù)即質(zhì)數(shù)和合數(shù)根據(jù)其分解結(jié)果計算目標(biāo)函數(shù)值再進(jìn)行比較或統(tǒng)計。 這類題目綜合考察了篩法、數(shù)論、甚至簡單數(shù)據(jù)結(jié)構(gòu)的能力是區(qū)分選手水平的關(guān)鍵。4. 實戰(zhàn)編碼以“區(qū)間質(zhì)數(shù)個數(shù)統(tǒng)計”為例的完整實現(xiàn)與避坑指南現(xiàn)在讓我們拋開對原題的猜測聚焦于“區(qū)間質(zhì)數(shù)個數(shù)統(tǒng)計”這個最可能的核心模型寫一份健壯、高效的代碼并聊聊其中容易出錯的地方。4.1 算法步驟詳解與C實現(xiàn)假設(shè)問題為給定T組詢問每組詢問包含兩個整數(shù)L, R (1 ≤ L ≤ R ≤ 10^12, R-L ≤ 10^6, T ≤ 10)求[L, R]內(nèi)的質(zhì)數(shù)個數(shù)。步驟拆解預(yù)處理小質(zhì)數(shù)利用線性篩篩出所有小于等于sqrt(MAX_R)的質(zhì)數(shù)。由于R最大為10^12sqrt(R)最大為10^6所以我們篩到10^6即可。處理每組詢問 a. 創(chuàng)建一個布爾數(shù)組is_prime大小為R-L1初始全部設(shè)為true。注意這個數(shù)組的下標(biāo)0對應(yīng)數(shù)字L下標(biāo)k對應(yīng)數(shù)字Lk。 b. 對于每一個我們預(yù)處理出的小質(zhì)數(shù)p - 計算在區(qū)間[L, R]內(nèi)第一個能被p整除的數(shù)。這可以通過公式start max(p * p, ((L p - 1) / p) * p)來計算。(L p - 1) / p是向上取整的除法得到的是大于等于L的第一個p的倍數(shù)。但要注意如果這個倍數(shù)是p本身即p L那么p是質(zhì)數(shù)不應(yīng)該被標(biāo)記。所以我們要從max(p*p, ...)開始確保了如果p在區(qū)間內(nèi)它自身不會被篩掉。 - 從start開始以p為步長遍歷并將is_prime[start - L],is_prime[start - L p], ... 標(biāo)記為false。 c. 遍歷is_prime數(shù)組統(tǒng)計其中值為true的個數(shù)。注意如果L等于1需要特殊處理因為1不是質(zhì)數(shù)但我們的算法可能不會將其標(biāo)記為false因為沒有任何質(zhì)數(shù)能篩掉1。所以通常需要在初始化或統(tǒng)計時手動將1排除。C代碼實現(xiàn)#include iostream #include vector #include cmath using namespace std; const int MAX_SIEVE 1000000; // 篩到10^6因為sqrt(10^12)10^6 vectorint primes; // 存儲預(yù)處理的小質(zhì)數(shù) vectorbool is_prime_small; // 線性篩預(yù)處理 void linear_sieve(int n) { is_prime_small.resize(n 1, true); is_prime_small[0] is_prime_small[1] false; for (int i 2; i n; i) { if (is_prime_small[i]) { primes.push_back(i); } for (size_t j 0; j primes.size() i * primes[j] n; j) { is_prime_small[i * primes[j]] false; if (i % primes[j] 0) break; } } } // 區(qū)間篩法統(tǒng)計 [L, R] 內(nèi)質(zhì)數(shù)個數(shù) long long count_primes_in_range(long long L, long long R) { if (L R) return 0; int len R - L 1; vectorbool is_prime_big(len, true); // 區(qū)間數(shù)組 for (int p : primes) { if ((long long)p * p R) break; // 小優(yōu)化質(zhì)數(shù)平方超過R后續(xù)不可能篩掉區(qū)間內(nèi)任何數(shù) // 計算起始位置 // start 是大于等于L的第一個p的倍數(shù)且至少是p*p long long start max((long long)p * p, ((L p - 1) / p) * p); for (long long j start; j R; j p) { is_prime_big[j - L] false; } } // 特殊處理L1的情況 if (L 1) { is_prime_big[0] false; // 1不是質(zhì)數(shù) } // 統(tǒng)計 long long cnt 0; for (int i 0; i len; i) { if (is_prime_big[i]) { cnt; } } return cnt; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); linear_sieve(MAX_SIEVE); // 預(yù)處理 int T; cin T; while (T--) { long long L, R; cin L R; cout count_primes_in_range(L, R) \n; } return 0; }4.2 關(guān)鍵細(xì)節(jié)與常見“坑點”在實際編寫和調(diào)試這類代碼時以下幾個細(xì)節(jié)至關(guān)重要一不留神就會導(dǎo)致錯誤或超時數(shù)據(jù)類型溢出這是最大的“坑”。L、R、start、j這些變量在計算p*p或((L p - 1) / p) * p時極容易超出int的范圍。務(wù)必使用long long類型。在C中即使p是int(long long)p * p也會先將p提升為long long再計算避免溢出。起始位置計算start max(p * p, ((L p - 1) / p) * p)這個公式需要理解透徹。(L p - 1) / p是整數(shù)除法實現(xiàn)向上取整的技巧。確保這個計算在long long類型下進(jìn)行。1的特殊處理我們的篩法是基于“合數(shù)有小于等于其平方根的質(zhì)因子”這一原理。1不符合這個條件所以它永遠(yuǎn)不會被標(biāo)記為false。必須在統(tǒng)計前手動判斷并排除。內(nèi)存與性能區(qū)間數(shù)組is_prime_big的大小是R-L1題目通常保證這個值在可接受范圍內(nèi)如10^6。使用vectorbool可以有效節(jié)省內(nèi)存通常每個元素占1 bit。在標(biāo)記合數(shù)時內(nèi)層循環(huán)for (long long j start; j R; j p)的步長是p這是一個相對較慢的操作尤其是在p很小的時候。但鑒于區(qū)間長度和質(zhì)數(shù)個數(shù)有限整體復(fù)雜度仍是可接受的。預(yù)處理范圍預(yù)處理小質(zhì)數(shù)的范圍是sqrt(MAX_R)而不是MAX_R。這是區(qū)間篩法的理論依據(jù)篩得過多純屬浪費時間和空間。5. 調(diào)試與驗證如何確保你的解法是正確的對于算法競賽題目尤其是數(shù)學(xué)相關(guān)的題目不能僅憑樣例通過就認(rèn)為萬事大吉。以下是我常用的幾種驗證策略暴力對拍針對小數(shù)據(jù)范圍例如L, R 10^5寫一個最樸素的質(zhì)數(shù)判斷函數(shù)與你的區(qū)間篩法結(jié)果進(jìn)行對比。生成大量隨機(jī)數(shù)據(jù)運行兩個程序比較輸出是否一致。這是發(fā)現(xiàn)邊界條件和邏輯錯誤最有效的方法。利用已知結(jié)果查詢一些已知的質(zhì)數(shù)計數(shù)結(jié)果例如π(10^6) 78498, π(10^7) 664579。你可以讓自己的程序計算[1, 10^6]的質(zhì)數(shù)個數(shù)看是否匹配。單步調(diào)試與中間輸出對于一組特定的數(shù)據(jù)可以輸出中間變量。例如輸出所有預(yù)處理出的小質(zhì)數(shù)看是否正確。對于某個質(zhì)數(shù)p輸出計算出的start值看是否合理。甚至可以輸出區(qū)間數(shù)組被標(biāo)記的過程觀察合數(shù)是否被正確篩掉。壓力測試雖然題目給了參數(shù)范圍但自己可以測試極限數(shù)據(jù)例如L999999000001, R1000000000000一個長度為10^6的區(qū)間靠近10^12。檢查程序運行時間和內(nèi)存使用是否在預(yù)期內(nèi)以及結(jié)果是否合理可以通過估算質(zhì)數(shù)密度來粗略判斷。注意在競賽環(huán)境中通常要關(guān)閉調(diào)試輸出并確保輸入輸出效率。使用ios::sync_with_stdio(false); cin.tie(nullptr);可以顯著加速C的cin/cout。6. 舉一反三如何應(yīng)對未知的“prime”變體題目面對一道只有標(biāo)題和少量信息的“prime”題在競賽中的解題策略應(yīng)該是仔細(xì)閱讀題目描述這是廢話但也是最重要的一步。明確題目要求我們做什么計數(shù)求和查找構(gòu)造分析數(shù)據(jù)范圍這是決定算法的關(guān)鍵。如果R最大只有10^6那么直接線性篩預(yù)處理整個范圍即可。如果R大到10^12但區(qū)間長度小就用區(qū)間篩。如果涉及到數(shù)字的各位二進(jìn)制或十進(jìn)制可能要考慮數(shù)位DP。識別核心模型判斷題目是單純的質(zhì)數(shù)判定/篩選還是質(zhì)數(shù)作為過濾條件如popcount是質(zhì)數(shù)或是與質(zhì)因數(shù)分解相關(guān)的結(jié)構(gòu)性問題。將陌生問題映射到已知模型。設(shè)計算法流程基于模型和數(shù)據(jù)范圍設(shè)計出主體算法框架。思考需要預(yù)處理什么質(zhì)數(shù)表、前綴和、DP狀態(tài)等查詢?nèi)绾位卮稹Ｗ⒁鈨?yōu)化點例如多個詢問時預(yù)處理是否可以共享統(tǒng)計是否需要用到前綴和篩法是否有優(yōu)化空間如只篩奇數(shù)編寫與測試先實現(xiàn)核心函數(shù)如區(qū)間篩用暴力方法驗證正確性。然后再集成到完整解題邏輯中。以“prime”為名的題目其內(nèi)核往往是清晰的數(shù)論知識。扎實掌握線性篩、區(qū)間篩、質(zhì)因數(shù)分解、前綴和與數(shù)位DP這些基礎(chǔ)工具并培養(yǎng)通過數(shù)據(jù)范圍反推算法的能力就能在遇到這類題目時游刃有余。這道“JZOJ6825”具體是什么或許已不重要重要的是通過這個標(biāo)題我們系統(tǒng)地梳理和鞏固了一類重要的算法思想與實現(xiàn)技巧這才是備賽和提升的真正意義。