题目重点：证明 1 不是质数、试除只需到平方根，并用埃氏筛一次生成闭区间内的全部质数。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版输出闭区间 [1,200] 中所有正质数，升序；1 不是质数，2 和 3 是质数。
- 质数定义为大于 1 且只有 1 和自身两个正因子的整数。
- 200 是题面明确固定上界；推广到 N 时需考虑 N 的规模与内存。
解题路线
- 若只检查某个 n，试除 d=2..floor(sqrt(n)) 即可：若有更大因子，其配对因子必不超过 sqrt(n)。
- 一次求范围内所有质数时建 0..200 布尔表，先标 0、1 非质数；依次从 2 到 sqrt(200) 处理尚未划掉的 p。
- 对每个 p 从 p² 开始以步长 p 标合数，因为小于 p² 的 p 倍数早已被更小因子划掉；最后按升序输出仍为 True 的位置。
- 正确性：每个合数有 ≤sqrt(N) 的质因子，因此至少被某一轮标掉；真正质数不是其他更小正数的倍数，不会被标掉。
手动走一遍
p=2 从 4、6、8… 标；p=3 从 9、12、15… 标。1 一开始就置 False，2 和 3 保持 True；200 被 2 标掉。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Return primes in the inclusive range 1..200 using a sieve."""
def primes_to_200() -> list[int]:
upper = 200
prime = [True] * (upper + 1)
prime[0] = prime[1] = False
for candidate in range(2, int(upper ** 0.5) + 1):
if not prime[candidate]:
continue
for composite in range(candidate * candidate, upper + 1, candidate):
prime[composite] = False
return [value for value in range(2, upper + 1) if prime[value]]
复杂度
固定 200 是常数；推广上界 N：埃氏筛 O(N log log N) 时间、O(N) 空间，逐个试除约 O(N√N) 最坏时间、O(1) 附加空间。
易错点与追问
容易失分的边界
- 把 1 当质数。
- 只遍历奇数而忘记输出 2。
- 把 sqrt 上界写成严格小于，漏掉完全平方数。
- 题目数组重复值规则不完整，却硬合并为质数题追问。
继续深挖
- N 很大但内存有限时如何做分段筛？
- 只判断一个大整数是否质数时为什么不必筛整段？
- 为什么从 p² 开始标合数仍完整？
