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