✅ PAT 乙级题目讲解1007《素数对猜想》 摘要本文详细讲解了 PAT 乙级 1007 题「素数对猜想」的完整解题过程。题目要求统计不超过 N 的素数对差值为 2 的相邻素数个数。文章采用埃拉托色尼筛法高效筛选素数再通过枚举奇数判断素数对时间复杂度优化至 O(N log log N)其中 N ≤ 10⁵。同时总结了常见易错点暴力判断超时、枚举边界错误、标记逻辑混淆等并拓展介绍了孪生素数猜想与更高效的筛法优化方向。 题目简介本题考察的是数论中的一个经典问题素数对猜想。题目定义了所谓“素数对”是指一对相邻的素数差值为 2例如 (3, 5)、(5, 7)、(11, 13) 等。我们需要找出所有不超过给定正整数NNN的这样的素数对个数。数据范围1≤N1051 \leq N 10^51≤N105。 样例分析输入20分析过程不超过 20 的所有素数为2, 3, 5, 7, 11, 13, 17, 19素数对为(3, 5)(5, 7)(11, 13)(17, 19)共有 4 对。因此输出为4 解题思路 变量说明变量名含义n输入的正整数 Na[i]布尔数组标记i是否为合数false表示质数ans满足条件的素数对个数本题求解可分为以下步骤✅ Step 1用筛法筛选出所有不超过nnn的素数筛法思路初始时将所有数标记为“可能是质数”即a[i] false。从222到n\sqrt{n}n​枚举每一个数iii若iii仍为质数即a[i] false则将所有iii的倍数标记为合数即a[j] true。for(inti2;i*in;i){if(!a[i]){for(intj2*i;jn;ji){a[j]1;// 标记为合数}}}✅ Step 2枚举所有奇数判断 (i, i2) 是否为素数对由于除了 2 以外所有质数都是奇数因此我们从 3 开始枚举每个奇数iii。若iii和i2i2i2都是质数即a[i] false且a[i2] false则计数器加 1。for(inti3;i2n;i2){if(!a[i]!a[i2]){ans;}}✅ 完整代码#includebits/stdc.husingnamespacestd;intn;boola[100005];// a[i] false 表示 i 是质数intmain(){scanf(%d,n);for(inti2;i*in;i){if(!a[i]){for(intj2*i;jn;ji){a[j]1;}}}intans0;for(inti3;i2n;i2){if(!a[i]!a[i2]){ans;}}printf(%d,ans);return0;} 常见错误提醒错误类型具体表现判断质数方法错误使用2∼n−12 \sim n-12∼n−1暴力判断质数会超时忘记从 3 开始枚举由于 (2, 4) 不是素数对应从 3 开始枚举未判断 i2 是否超过 n枚举上界应为i 2 n素数标记逻辑相反错误地认为true是素数导致答案反了✅ 总结归纳本题是典型的素数筛法应用题。筛法的核心是利用质因数性质反向标记合数。巧妙地从 3 开始步长为 2 枚举可能的素数对提高效率。注意标记逻辑中false才代表质数这是很多初学者易错之处。 思维拓展素数对猜想孪生素数猜想猜想存在无限多对差为 2 的素数对至今尚未被证明。本题是该猜想的有限模型在范围[1,n][1, n][1,n]中寻找所有“孪生素数”。可进一步探究欧拉筛优化、线性筛等更高效的素数判定算法。