质数与合数真题汇总与解析

这个考点在真题里怎么考

「质数与合数」在信息学竞赛真题中出现 7 次，覆盖 NOIP 普及组初赛、CSP 入门级、CSP 提高级。下面按考试级别列出每一道题的题号、答案与一句话解题思路，可以按考点横向刷，也可以顺着套卷纵向练。

怎么用这一页：先看下面的「命中题目速查」，挑 2~3 道做；做完对照每题的「常见错误」检查自己是不是踩了同一个坑；同一个考点连续错两次，就去知识点精讲把规则补齐再回来刷。

NOIP 普及组初赛（1 道）

第 27 题 答案：tmp=1tmp=truep[j]p[r]=ip[j]+p[k]p[k]+p[j]1004 · 完善程序 · NOIP 2010 普及组初赛试题

这题核心是筛质数再验证哥德巴赫猜想。先理清数组p存的是前r个质数，筛数时tmp默认true，若被p[j]整除则tmp变false；验证时只要找到一对p[j]+p[k]==2i即可计数。

CSP-J 入门级（4 道）

第 9 题 答案：B · 选择题 · CSP 2019 入门级第一轮

这题考素数判定。别傻乎乎从2数到100，直接从100往下倒着看，遇到第一个既不能被2、3、5、7整除的数就是答案。

第 19 题 答案：CA · 完善程序 · CSP 2020 入门级第一轮

这题考质因数分解，核心就是从小到大枚举i，用i反复试除n，直到i i n为止，最后若n仍大于1则说明剩余一个大于根号n的质因子。

第 16 题 答案：AB · 阅读程序 · CSP 2024 入门级第一轮

这题核心就是理解素数判断算法的边界条件和循环效率。拿到题先跑一遍代码看输入10时的素数2,3,5,7，再想命题人改循环条件是想考你对‘因子成对出现’和‘最大因子一定小于等于n/2’这两个性质的理解，别被表面改动迷惑。

第 18 题 答案：BADC · 阅读程序 · CSP 2026 入门级第一轮

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

CSP-S 提高级（2 道）

第 17 题 答案：BAD · 阅读程序 · CSP 2023 提高级第一轮

这题核心是读懂一个带小优化的埃氏筛，再会算两个数论求和。先看 solve1 里对每个质数幂 k 把倍数 j 标记为合数，同时记录 g[j]=k（k 是 j 的最大质数幂因子）；后面用 g 把 f 变成前缀积，再求和。so…

第 18 题 答案：ABC · 阅读程序 · CSP 2024 提高级第一轮

这题核心是把筛质数、双哈希构建和二叉树合并揉在一起考。拿到题先看 init 里 p1[p2] 是干嘛的（底数幂），再看 solve 里 h[i] 怎么拼（左根右），最后排序去重。关键就是识别出合并顺序对应中序遍历，以及时…

想系统练这个考点？

在 OI伴学里按知识点学习树顺序推进——先学讲解、再做例题、最后配套练习，做错的题会自动归集。

质数与合数 真题汇总与解析