GESP 六级 · GESP 202312 C++ 六级 第 14 题

小杨想编写一个判断任意输入的整数 $N$ 是否为素数的程序，下面哪个方法不合适？（ ）

这题本质是考算法场景匹配。判断单个素数用枚举试除最自然，筛法能批量标记后 O(1) 查询也合适，唯独二分答案需要单调性，而素数分布毫无单调可言，直接排除 C。

很多考生看到‘筛法’就以为只能批量处理，单点判断用不上，其实筛完数组后查一个数就是 O(1)，A、B、D 都是能用的。真正坑的是 C，容易把‘二分’当成万能搜索技巧，误以为素数有某种单调性或者把‘判断素数’混淆成‘找第 k 个素数’，后者才可能二分。题目里没给任何单调性提示，却让你识别出二分答案的荒谬性，这就是陷阱。

考点定位与命题视角

这道题考查的是算法方法与其适用场景的匹配能力，核心知识点是质数判定、筛法（埃氏筛、线性筛）以及二分答案的适用条件。命题人故意把三种不同思路混在一起：埃氏筛和线性筛属于数论专用，通过预处理批量标记素数；枚举法是单次判定的暴力试除；二分答案则是利用单调性猜分界点的通用搜索技巧。六级要求考生能区分哪些是数论专用、哪些是通用搜索，很多考生看到‘素数’就只会写 O(√N) 枚举，根本没想到筛法才是批量处理素数的正解，或者误以为二分能用来找素数位置。

解题心法：拿到题先想什么？

拿到‘判断任意整数 N 是否为素数’这种描述，第一反应应该是：单次查询最自然的做法是什么？显然是枚举 2 到 √N 试除，复杂度 O(√N)，这就是 D 选项，完全合适。 那筛法呢？埃氏筛和线性筛都是用来批量筛出一段区间内的素数。如果你提前预处理好一个足够大的素数表（比如筛到 10^6），那么对任意输入的 N，只要 N 在表范围内，直接查表 O(1) 就能知道是不是素数。题目并没有限定 N 的范围，但作为‘方法’，筛法本身确实能给出答案，所以 A、B 也是合适的。 二分答案呢？二分的前提是存在单调性：随着输入变化，答案要么单调递增要么单调递减，这样我们才能通过不断缩小区间来逼近正确答案。素数分布完全没有这种性质——2 是素数，3 是素数，4 不是，5 是，6 不是……毫无规律可言。即使你强行想‘找第 k 个素数’，题目也没说‘第 k 个’，只说了‘任意输入的 N’。所以 C 选项在逻辑上根本行不通。