這是 GESP 2023年6月 的一道循環(huán)結(jié)構(gòu)題。題目本身不難但有幾個(gè)地方特別容易出錯(cuò)我把踩過的坑都寫出來希望能幫剛學(xué)到這里的朋友少走彎路。題目來源ACGO A46102 2023年6月 二級(jí)賽事場(chǎng)次2023年6月 二級(jí)一、題目信息題目名稱找素?cái)?shù)賽事場(chǎng)次2023年6月 二級(jí)難度定位二級(jí)涉及知識(shí)點(diǎn)循環(huán)結(jié)構(gòu)題目鏈接https://www.acgo.cn/problemset/info/46102坑點(diǎn)預(yù)警這里最容易失分循環(huán)三要素初值、條件、步進(jìn)循環(huán)不變式。題意簡(jiǎn)述小明剛剛學(xué)習(xí)了素?cái)?shù)的概念如果一個(gè)大于 1 的正整數(shù)除了 1 和它自身外不能被其他正整數(shù)整除則這個(gè)正整數(shù)是素?cái)?shù)?，F(xiàn)在小明想找到兩個(gè)正整數(shù)A和B之間包括A和B有多少個(gè)素?cái)?shù)前置知識(shí)做題之前我們先把幾個(gè)關(guān)鍵概念說清楚這樣后面的代碼才好理解。for 循環(huán)的標(biāo)準(zhǔn)寫法for(int i1;in;i)表示 i 從 1 遞增到 n每次循環(huán)體執(zhí)行完 i 自動(dòng)加 1。競(jìng)賽中我們習(xí)慣從 1 開始計(jì)數(shù)這樣可以避免下標(biāo)越界的麻煩。while 循環(huán)適合循環(huán)次數(shù)不確定的場(chǎng)景只要條件成立就一直執(zhí)行寫的時(shí)候一定要確保循環(huán)變量會(huì)被修改否則會(huì)死循環(huán)。二、思路分析先看清楚題目要我們做什么把題目讀兩遍我們提取出關(guān)鍵信息輸入是什么、要輸出什么、有哪些約束條件。這道題考查的是循環(huán)結(jié)構(gòu)屬于這類題里比較基礎(chǔ)的一道把題目要求一步步翻譯成代碼邏輯就能解決。我的思考過程讀完題之后我的第一反應(yīng)是這樣的【題目大意】統(tǒng)計(jì)整數(shù) A 到 B 范圍內(nèi)的素?cái)?shù)個(gè)數(shù)數(shù)據(jù)范圍不超過 1000?！究季V知識(shí)點(diǎn)】多層分支/循環(huán)結(jié)構(gòu)二級(jí)【解題思路】枚舉 A 到 B依次檢查每個(gè)數(shù)是不是素?cái)?shù)。用變量 isPrime 表示當(dāng)前枚舉的數(shù) n 是否為素?cái)?shù)初始化為 true如果找到了除了 1 和 n 以外的因數(shù)則把 isPrime 賦值為 false。尋找 n 的因數(shù)時(shí)只需要枚舉 2 到根號(hào) n。因?yàn)槿绻?n 有一個(gè)大于根號(hào) n 的因數(shù) k那么就一定存在一個(gè)小于根號(hào) n 的因數(shù) n/k。使用變量 cnt 記錄素?cái)?shù)的個(gè)數(shù)最終輸出即可?！緟⒖汲绦颉啃枰f明的是上面這個(gè)思路是把題目要求直譯成代碼得到的沒有用到什么高級(jí)技巧。對(duì)于這類基礎(chǔ)題讀準(zhǔn)題意加寫對(duì)邊界比追求巧妙解法更重要因?yàn)榭荚嚴(yán)镞@種題是必須拿滿分的。三、完整代碼 逐行注釋#include iostream using namespace std; int main() { int a 0, b 0, cnt 0; cin a b; // 讀入 for (int n a; n b; n) { // 遍歷 bool isPrime true; // 假設(shè)初始 isPrime 的值為 true // 利用因數(shù)成對(duì)存在的性質(zhì)遍歷較小的因數(shù)判斷 n 是否為素?cái)?shù) for (int i 2; i * i n; i) { // 遍歷 if (n % i 0) { // 判斷 //若發(fā)現(xiàn) n 存在因數(shù)更改標(biāo)記 isPrime 并跳出循環(huán) isPrime false; break; } } //題目規(guī)定 n 不會(huì)為 1否則要特殊判斷1的情況 if (isPrime) // 判斷 cnt; //統(tǒng)計(jì)素?cái)?shù)個(gè)數(shù) } cout cnt endl; // 輸出 return 0; }四、代碼分段拆解代碼不長(zhǎng)但每一段都有講究我們分段拆開看。第一步引入頭文件#include iostream using namespace std;#include iostream提供輸入輸出功能using namespace std;讓我們能直接寫cin、cout而不用加前綴。這兩行是幾乎所有 C 程序的開頭照寫即可。第二步讀入數(shù)據(jù)cin a b;注意變量的類型要能裝下題目的數(shù)據(jù)。數(shù)據(jù)可能超過 21 億時(shí)要改用long long。第三步核心處理邏輯for (int n a; n b; n) { for (int i 2; i * i n; i) {這一段是整道題的關(guān)鍵也是循環(huán)結(jié)構(gòu)的體現(xiàn)。看循環(huán)的三個(gè)要素從哪里開始、什么時(shí)候結(jié)束、每次怎么變化。這三個(gè)要素任何一個(gè)寫錯(cuò)結(jié)果都會(huì)不對(duì)。第四步按要求輸出cout cnt endl;輸出格式必須和題目要求的完全一致。很多同學(xué)算法完全正確卻因?yàn)樯倭艘粋€(gè)換行或者空格多寡不對(duì)而 WA這種分丟得最可惜。五、實(shí)例模擬光看代碼可能還不夠直觀我們用題目的樣例實(shí)際跑一遍看看程序是怎么走的。以題目的第一組樣例為例樣例輸入2 10樣例輸出4把這份輸入代進(jìn)代碼程序會(huì)先把數(shù)據(jù)依次讀入然后進(jìn)入循環(huán)逐個(gè)判斷把滿足條件的值累積起來最后按格式輸出。建議你對(duì)照著代碼在紙上走一遍前兩次循環(huán)確認(rèn)自己對(duì)每一步的理解都和程序一致。題目另外還給了 1 組樣例做完之后建議把剩下的樣例都跑一遍全部通過再提交能避開大部分邊界問題。六、踩坑總結(jié)下面是做這道題時(shí)最容易出錯(cuò)的地方對(duì)照自己的代碼檢查一下變量類型選錯(cuò)雖然本題范圍不大但養(yǎng)成習(xí)慣——凡是不確定范圍時(shí)累加變量一律用long long成本為零但能保命。取余與整除混淆a % b取的是余數(shù)a / b取的是整數(shù)商兩個(gè)完全不同。判斷倍數(shù)關(guān)系用a % b 0寫成a / b 0就全錯(cuò)了。區(qū)間邊界取錯(cuò)題目說「L 到 R 之間包括兩端」循環(huán)就要寫for (int i L; i R; i)。寫成i R會(huì)漏掉最后一個(gè)數(shù)這是最常見的失分點(diǎn)。循環(huán)起點(diǎn)搞錯(cuò)題目說的是「正整數(shù)」循環(huán)要從 1 開始而不是從 0 開始差一個(gè)數(shù)就是 WA。輸出格式不符題目要求輸出幾行就輸出幾行行末換行、數(shù)字之間的空格都要嚴(yán)格對(duì)齊算法對(duì)了但格式錯(cuò)了同樣判 WA這種分丟得最冤。特殊情況沒特判把最小數(shù)據(jù)、最大數(shù)據(jù)、答案恰好等于 0 的情況各測(cè)一遍。特別是邊界輸入出題人最喜歡在這里設(shè)陷阱。七、知識(shí)點(diǎn)拓展最后總結(jié)一下這道題帶給我們的通用經(jīng)驗(yàn)本題考查循環(huán)結(jié)構(gòu)的基本寫法這類題在考試中屬于必得分項(xiàng)要練到能默寫。寫完代碼后建議自己造幾組邊界數(shù)據(jù)測(cè)試特別是最小值和最大值。同一知識(shí)點(diǎn)在不同場(chǎng)次反復(fù)出現(xiàn)把這道題的寫法吃透后面遇到同類題可以直接套用。八、適用人群如果你已經(jīng)掌握循環(huán)結(jié)構(gòu)的基本寫法這道題可以用來鞏固手感。以上就是這道題的全部?jī)?nèi)容。這個(gè)系列會(huì)按考試場(chǎng)次逐題更新覺得有幫助的話可以關(guān)注一下也歡迎在評(píng)論區(qū)留下你的解法。