CSP-J 入门级 · CSP 2026 入门级第一轮 第 18 题

【阅读程序3】

（质数搜索）

#include <iostream>
using namespace std;
bool check_prime(int x) {
    if (x <= 1) return false;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}
int n;
void search_result(int x) {
    if (!check_prime(x)) return;
    if (x >= n) {
        cout << x << endl;
        return;
    }
    for (int i = 0; i <= 9; i++) {
        search_result(x * 10 + i);
    }
}
int main() {
    cin >> n;
    for (int i = 1; i <= 9; i++) search_result(i);
    return 0;
}

程序在 DFS 枚举"右截断质数"：每个数自己要是质数，且不断删去末位后剩下的数也都要是质数。每走到一个 ≥ n 的数就输出并停止往下扩展，所以输出的是"父结点 < n 且自身 ≥ n"的那一批。

把程序误读成"输出 n 以内的所有质数"（第 13 行是 x >= n 不是 x <= n，方向恰好相反）；数行数时忘记 DFS 是先往深处走（233、239 会排在 29 前面）。

程序分析

bool check_prime(int x) {          // 试除法判质数，√x 上限
    if (x <= 1) return false;
    for (int i = 2; i * i <= x; i++) if (x % i == 0) return false;
    return true;
}
void search_result(int x) {
    if (!check_prime(x)) return;      // 第 12 行：自己不是质数 → 整棵子树剪掉
    if (x >= n) { cout << x << endl; return; }   // 第 13 行：已经够大 → 输出并停止加深
    for (int i = 0; i <= 9; i++) search_result(x * 10 + i);   // 第 17 行：接上一位数字
}
int main() { cin >> n; for (int i = 1; i <= 9; i++) search_result(i); }

程序到底在做什么

从首位 1～9 出发做深度优先搜索，每一步在末尾再接一位数字（只允许 0～9）。两个剪枝/终止条件：

• 第 12 行：当前数必须是质数，否则整棵子树直接返回；
• 第 13 行：当前数 ≥ n 时输出并返回，不再往下扩展。

所以"所有前缀都是质数"（等价地：不断删去末位得到的数都是质数）的数构成一棵搜索树；程序输出的是这棵树里首次跨过 n 的那一批，即满足

x 是质数、x 的每个前缀都是质数、x ≥ n，且 x 去掉末位后 < n（或 x 是一位数）

的所有 x，打印顺序 = DFS 顺序（首位 1→2→3…，每位数字 0→9）。

第 28 题（判断）

n = 10 时，输出的一定是两位数以上的"全前缀质数"：20～29 段有 23、29，30～39 段有 31、37，50～59 段有 53、59，70～79 段有 71、73、79。合计

23, 29, 31, 37, 53, 59, 71, 73, 79 → 9 行，不是 10 行。 答案：B（错误） ✓

第 29 题（判断）

n ≤ 5 时，DFS 一定会走到首位 i = 5 这个分支：check_prime(5) 为真，且 5 ≥ n 成立，于是直接输出 5。所以输出中一定包含 5。 答案：A（正确） ✓ （同理 n ≤ 7 时输出一定包含 7。）

第 30 题（判断）

把第 17 行改成只枚举奇数 for (int i = 1; i <= 9; i += 2)。当 n > 10 时，任何被输出的 x 都 ≥ n > 10 且是质数，大于 10 的质数末位只能是 1、3、7、9（全是奇数）；被剪掉的偶数末位分支（x*10+0/2/4/6/8）本身必然不是质数，进入后第 12 行就会立刻返回，不会产生任何输出。所以剪掉这些"死枝"不改变输出。 答案：A（正确） ✓

第 31 题（单选）

n = 24，按 DFS 顺序输出：

1. 首位 2 → 2 < 24，继续；10 个孩子里只有 23（质数）可扩展； 2. 23 < 24，继续 → 230…239 中质数只有 233、239 → 两者都 ≥ 24，分别输出（第 1、2 行）； 3. 回到首位 2 的孩子 29（质数且 < 24？不，29 ≥ 24）→ 第 3 行输出 29； 4. 之后才是 31、37、311、313、…

所以第 3 行是 29。 答案：B（29） ✓ （C 31 是第 4 行；A 23 是第 1 行的两个三位数之后才轮到，注意 DFS 会先把 23 的子树走完。）

第 32 题（单选）

逐项判断：

• A 错：输出不递增——233、239 排在 29 前面；
• B 错：n 变大输出行数不一定不增（n = 10 时 9 行，n = 24 时明显更多）；
• C 错：输出的个位还可能是 1、9（如 31、59、719）；
• D 对：这正是第 12 行剪枝的直接推论——输出的每个数都是质数，删去末位得到的前缀也必须是质数。

答案：D ✓

第 33 题（单选）

n = 200，输出的是"前两位为质数、自身 ≥ 200"的三位质数（因为三位数 ≥ 200 全部满足 ≥ n，而两位前缀都 < 200）。枚举所有两位全前缀质数 23, 29, 31, 37, 53, 59, 71, 73, 79 的质数孩子：

合计 2+1+3+2+0+2+1+2+1 = 14 行。 答案：C（14） ✓

本题小结

套路提示：DFS 枚举题先画出一棵搜索树，写清"哪些结点会被剪掉、哪些结点会立刻返回"。本题的两个终止条件（不是质数 / ≥ n）决定了树的形状，之后所有小题都只是在树上数结点或数列序。