质数判定与筛法
本节目标
区分单个整数的质数判定与范围内质数预处理，建立试除法和线性筛的选择标准。
质数问题先要问清输入规模：只有一个整数时，目标是尽快证明它没有非平凡因子；需要回答一个区间内的大量问题时，才值得一次性预处理全部质数。两种任务的数学依据相同，但计算方向完全不同。
识别信号
- 给定单个
n，询问它是否为质数，或只需检查少量候选数； - 给定上界
n，需要获得1..n的质数表、质数个数或后续的最小质因子； - 约束很大时，不能对范围内每个数都单独试除。
核心定义与不变量
大于 1 且只有 1 与自身两个正因子的整数是质数。若合数 n 能写成 a × b，就至少有一个因子不大于 √n；因此单次判断只要寻找这一侧的因子即可。
线性筛维护的关键不变量是：处理到 number 时，已有表按递增顺序保存已发现质数；把 number × prime 标为合数，并在 prime 整除 number 时停止。这样每个合数恰好由它的最小质因子标记一次。
朴素方法与瓶颈
从 2 枚举到 n - 1 判断整除，单个数需要 O(n)；把它重复用于 1..n 的每个整数会产生大量重复工作。埃氏筛先将质数的倍数划去，已能避免逐个判断；线性筛进一步避免同一合数被多个质数重复划去。
推导与实现框架
单次判断从 2 开始枚举 divisor，只要 divisor <= n / divisor。使用除法等价于比较 divisor² <= n，却不会在整数平方接近上界时溢出，也不把 sqrt 的浮点舍入边界带进循环条件。
批量筛法依次处理 2..n：未被标记的数就是新质数；再遍历当前质数表，标记乘积。若当前质数整除 number，它已是乘积的最小质因子，立即停止；否则继续让更大的质数参与。
复杂度与数值边界
试除法时间为 O(√n)、额外空间为 O(1)。线性筛时间为 O(n)，质数表与合数标记共使用 O(n) 空间。n < 2 必须直接判为非质数；乘积标记前先确认 prime <= n / number，避免计算 prime * number 时溢出。
母题序列
常见误区
- 把
1当成质数，或遗漏n < 2的提前返回。 - 直接以
sqrt(n)作为整数循环边界，忽略浮点结果在完全平方数附近可能产生的舍入问题。 - 在线性筛中不在
number % prime == 0时停止，导致同一合数被重复标记。 - 未先检查乘积范围，便计算可能溢出的
prime * number。
迁移方向
质数表还能服务于最小质因子分解、欧拉函数与组合数模运算。若只需要分解一个数，下一栏的试除法更直接；若需要许多查询的最小质因子，则可在筛法中额外记录该信息。