动机
为什么要列出素数?
许多计算需要列出不超过上界 N N N 的所有素数,而不只是判断一个整数。例如,我们可能要分解许多较小的数、编制算术函数表,或在一个初始范围内检验猜想。逐个测试整数会重复工作:91 = 7 ⋅ 13 91=7\cdot13 91 = 7 ⋅ 13 和 119 = 7 ⋅ 17 119=7\cdot17 119 = 7 ⋅ 17 都利用同一个素数 7 7 7 。埃拉托色尼(Eratosthenes)筛法把问题反过来:不问什么数整除 n n n ,而是对每个小素数 p p p ,问它整除哪些数。
本节要得到一张经过证明 的表:给出确定性的有限过程,并证明对每个满足 0 ≤ k ≤ N 0\le k\le N 0 ≤ k ≤ N 的整数 k k k ,过程报告它是素数当且仅当它确实是素数。
定义
素数、合数与两个特殊整数
整数 n n n 是素数 ,指 n ≥ 2 n\ge2 n ≥ 2 且其正因数只有 1 1 1 和 n n n 。大于等于 2 2 2 而不是素数的整数称为合数 。等价地,合数可写成 n = a b n=ab n = ab ,其中 a , b a,b a , b 为整数且 2 ≤ a ≤ b ≤ n − 1 2\le a\le b\le n-1 2 ≤ a ≤ b ≤ n − 1 。
整数 0 0 0 和 1 1 1 既非素数也非合数。每个整数都整除 0 0 0 ,因此 0 0 0 没有受到限制的因数结构。1 1 1 是单位;如果把它当成素数,唯一分解便会失效,因为 6 = 2 ⋅ 3 = 1 ⋅ 2 ⋅ 3 6=2\cdot3=1\cdot2\cdot3 6 = 2 ⋅ 3 = 1 ⋅ 2 ⋅ 3 。筛法必须明确处理 0 0 0 和 1 1 1 :定义已将它们排除,而划去素数的倍数不会触及它们。
对 k ≥ 2 k\ge2 k ≥ 2 ,记 lpf ( k ) \operatorname{lpf}(k) lpf ( k ) 为 k k k 的最小素因数 。素因数分解保证它存在。注意,lpf ( k ) = k \operatorname{lpf}(k)=k lpf ( k ) = k 当且仅当 k k k 为素数。
若 k k k 是合数,则 lpf ( k ) 2 ≤ k \operatorname{lpf}(k)^2\le k lpf ( k ) 2 ≤ k 。特别地,每个不超过 N N N 的合数都有一个不超过 N \sqrt N N 的素因数 q q q 。
写 k = a b k=ab k = ab ,其中 2 ≤ a ≤ b 2\le a\le b 2 ≤ a ≤ b ,则 a 2 ≤ a b = k a^2\le ab=k a 2 ≤ ab = k 。由于 a ≥ 2 a\ge2 a ≥ 2 ,a a a 有素因数 q ≤ a q\le a q ≤ a 。由 q ∣ a ∣ k q\mid a\mid k q ∣ a ∣ k ,得 lpf ( k ) ≤ q ≤ a \operatorname{lpf}(k)\le q\le a lpf ( k ) ≤ q ≤ a ,因此 lpf ( k ) 2 ≤ a 2 ≤ k \operatorname{lpf}(k)^2\le a^2\le k lpf ( k ) 2 ≤ a 2 ≤ k 。若进一步有 k ≤ N k\le N k ≤ N ,则 lpf ( k ) 2 ≤ N \operatorname{lpf}(k)^2\le N lpf ( k ) 2 ≤ N ,得到所述推论。
还需要一个算术事实。对整数 p ≥ 1 p\ge1 p ≥ 1 和 N ≥ 0 N\ge0 N ≥ 0 ,
p 2 ≤ N ⟺ p ≤ ⌊ N / p ⌋ . p^2\le N\iff p\le\left\lfloor N/p\right\rfloor . p 2 ≤ N ⟺ p ≤ ⌊ N / p ⌋ .
正向由 p ≤ N / p p\le N/p p ≤ N / p 及 p p p 为整数得到;反向由 p ≤ ⌊ N / p ⌋ ≤ N / p p\le\lfloor N/p\rfloor\le N/p p ≤ ⌊ N / p ⌋ ≤ N / p 得到。在实际机器上右侧形式很重要,因为它不计算可能溢出的乘积。
算法与机器模型
模型。 设机器字可存储 0 , 1 , … , 2 w − 1 0,1,\dots,2^w-1 0 , 1 , … , 2 w − 1 ,其中整数 w ≥ 1 w\ge1 w ≥ 1 。字上的加、减、乘、向下取整除法、比较及数组访问各耗一步。可分配的数组长度还有上限 L L L ;整数和内存都不是无限的。输入必须满足
0 ≤ N ≤ 2 w − 1 且 N + 1 ≤ L . 0\le N\le2^w-1\quad\text{且}\quad N+1\le L. 0 ≤ N ≤ 2 w − 1 且 N + 1 ≤ L .
需要分配数组时,索引为 0 , 1 , … , N 0,1,\dots,N 0 , 1 , … , N ,所以要 N + 1 N+1 N + 1 个单元;检查长度条件时也不能溢出:例如采用更宽的长度类型,或在 L > 0 L>0 L > 0 时比较 N < L N<L N < L 。若上述前提不满足,过程必须拒绝输入,不能悄悄回绕。即使两个提前返回的情形不需要数组,这仍是一个充分的输入约定。
常见错误
(分配 N N N 个而不是 N + 1 N+1 N + 1 个单元)
索引为 0 , 1 , … , N 0,1,\dots,N 0 , 1 , … , N ,所以数组需要 N + 1 N+1 N + 1 个单元。只有 N N N 个单元时会遗漏索引 N N N :对 N = 49 N=49 N = 49 ,最后一次写入 mark [ 49 ] : = false \texttt{mark}[49]:=\text{false} mark [ 49 ] := false 落在数组之外;对素数输入如 N = 47 N=47 N = 47 ,最大的素数永远不会被报告。
SIEVE(N)
要求 0 ≤ N,N 能放入一个机器字,且能分配 N + 1 个单元
若 N ≤ 1:返回空表
分配 mark[0..N] # N + 1 个布尔单元
对 k := 0 到 N: # 在 k = N 后停止,不产生 N + 1
mark[k] := (k ≥ 2)
p := 2
当 p ≤ floor(N / p): # 等价于 p*p ≤ N,但不会溢出
若 mark[p]:
m := p * p # 安全:p*p ≤ N
循环:
mark[m] := false
若 m > N - p:退出循环 # 下一个倍数将超过 N
m := m + p # 安全:m + p ≤ N
p := p + 1
返回满足 0 ≤ k ≤ N 且 mark[k] = true 的全部 k
溢出检查。 当 N < 2 N<2 N < 2 时,过程在形成 p = 2 p=2 p = 2 之前返回。对 N ≥ 2 N\ge2 N ≥ 2 ,以下机器字索引及算术中间值均在 [ 0 , N ] [0,N] [ 0 , N ] 内;分配长度 N + 1 N+1 N + 1 另行检查:
⌊ N / p ⌋ ≤ N \lfloor N/p\rfloor\le N ⌊ N / p ⌋ ≤ N ;
只有确定 p 2 ≤ N p^2\le N p 2 ≤ N 后才计算 p ⋅ p p\cdot p p ⋅ p ;
因为 p ≤ p 2 ≤ N p\le p^2\le N p ≤ p 2 ≤ N ,所以 N − p ≥ 0 N-p\ge0 N − p ≥ 0 ;
只有 m ≤ N − p m\le N-p m ≤ N − p 时才计算 m + p m+p m + p ;
执行 p : = p + 1 p:=p+1 p := p + 1 时有 p 2 ≤ N p^2\le N p 2 ≤ N ,所以 p + 1 ≤ N p+1\le N p + 1 ≤ N 。
因此这些机器字运算不需要大于 N N N 的数,但长度类型仍可能需要表示 N + 1 N+1 N + 1 。
正确性
余下的证明假设 N ≥ 2 N\ge2 N ≥ 2 。设 s = ⌊ N ⌋ s=\lfloor\sqrt N\rfloor s = ⌊ N ⌋ ,即满足 s 2 ≤ N s^2\le N s 2 ≤ N 的最大整数。根据上面的等价式,外层循环处理 p = 2 , 3 , … , s p=2,3,\dots,s p = 2 , 3 , … , s ,并在 P = max ( 2 , s + 1 ) P=\max(2,s+1) P = max ( 2 , s + 1 ) 处停止。
引理 9.1.3
(不变量 I ( p ) I(p) I ( p ) )
每次以当前值 p p p 测试循环条件之前:
(a) 对每个素数 k ≤ N k\le N k ≤ N ,mark [ k ] \texttt{mark}[k] mark [ k ] 为真;
(b) mark [ 0 ] \texttt{mark}[0] mark [ 0 ] 和 mark [ 1 ] \texttt{mark}[1] mark [ 1 ] 为假(若对应索引存在);
(c) 对每个满足 lpf ( k ) < p \operatorname{lpf}(k)\lt p lpf ( k ) < p 的合数 k ≤ N k\le N k ≤ N ,mark [ k ] \texttt{mark}[k] mark [ k ] 为假。
初始情形 p = 2 p=2 p = 2 。 初始化将 k ≥ 2 k\ge2 k ≥ 2 的位置设为真,将 0 , 1 0,1 0 , 1 设为假,故 (a)、(b) 成立。每个最小素因数都至少为 2 2 2 ,故 (c) 真空成立。
归纳步。 假设 I ( p ) I(p) I ( p ) 成立且循环体执行,因此 p 2 ≤ N p^2\le N p 2 ≤ N 。
情形一:p p p 是合数。 小素因数引理给出 lpf ( p ) ≤ p < p \operatorname{lpf}(p)\le\sqrt p\lt p lpf ( p ) ≤ p < p ;由 (c),mark [ p ] \texttt{mark}[p] mark [ p ] 为假,循环体不改变任何标记。若合数 k k k 的最小素因数小于 p + 1 p+1 p + 1 ,它不能等于合数 p p p ,所以已经小于 p p p 。因此 I ( p ) I(p) I ( p ) 蕴含 I ( p + 1 ) I(p+1) I ( p + 1 ) 。
情形二:p p p 是素数。 由 (a),mark [ p ] \texttt{mark}[p] mark [ p ] 为真。内层循环从 p 2 ≤ N p^2\le N p 2 ≤ N 开始,每次加 p p p ,当下一个值将超过 N N N 时退出。因此它恰好划去 [ p 2 , N ] [p^2,N] [ p 2 , N ] 内的 p p p 的倍数。
每个被划去的数都是 p j pj p j ,其中 j ≥ p ≥ 2 j\ge p\ge2 j ≥ p ≥ 2 ,所以它是至少为 4 4 4 的合数。没有素数、0 0 0 或 1 1 1 被触及,故 (a)、(b) 保持成立。
对 (c),设合数 k ≤ N k\le N k ≤ N 满足 lpf ( k ) = p \operatorname{lpf}(k)=p lpf ( k ) = p ,写 k = p j k=pj k = p j 。因为 k ≠ p k\ne p k = p ,有 j ≥ 2 j\ge2 j ≥ 2 ;j j j 的每个素因数也整除 k k k ,因而至少为 p p p 。所以 j ≥ p j\ge p j ≥ p ,k ≥ p 2 k\ge p^2 k ≥ p 2 ,故 k k k 刚被划去。结合 I ( p ) I(p) I ( p ) ,便得到 I ( p + 1 ) I(p+1) I ( p + 1 ) 。
对满足前提的每个整数 N N N ,SIEVE ( N ) \operatorname{SIEVE}(N) SIEVE ( N ) 都会终止,返回的恰好是 0 ≤ k ≤ N 0\le k\le N 0 ≤ k ≤ N 的全部素数。
外层每次将 p p p 增加 1 1 1 ,内层每次严格增大有上界 N N N 的 m m m ,所以过程终止。退出时 I ( P ) I(P) I ( P ) 成立。
由 (a) 所有素数均被报告;由 (b) 0 , 1 0,1 0 , 1 不被报告。对任意合数 k ≤ N k\le N k ≤ N ,小素因数引理给出 lpf ( k ) ≤ N \operatorname{lpf}(k)\le\sqrt N lpf ( k ) ≤ N ,因此 lpf ( k ) ≤ s < P \operatorname{lpf}(k)\le s\lt P lpf ( k ) ≤ s < P 。由 (c),k k k 不被报告。
当 N < 2 N<2 N < 2 ,提前返回空表是正确的,因为小于 2 2 2 的数中没有素数。当 N = 2 N=2 N = 2 或 N = 3 N=3 N = 3 ,循环也不执行;这是正确的,因为此范围内没有合数。
证明透视
不变量如何认证整个列表 小素因数引理用了两次。在归纳步中,它说明合数 p p p 已被划去,所以循环体不改变任何标记;在完备性一步中,它说明每个合数 k ≤ N k\le N k ≤ N 都有 lpf ( k ) ≤ s < P \operatorname{lpf}(k)\le s\lt P lpf ( k ) ≤ s < P 。
关键一步是按最小素因数来索引 (c)。处理素数 p p p 时,(c) 新要求的合数只有满足 lpf ( k ) = p \operatorname{lpf}(k)=p lpf ( k ) = p 的那些,而每个都是 p j pj p j ,其中 j ≥ p j\ge p j ≥ p 。这就是内层循环可以从 p 2 p^2 p 2 开始的原因:2 ≤ j < p 2\le j\lt p 2 ≤ j < p 的倍数 p j pj p j 含有 j j j 的一个小于 p p p 的素因数,由 I ( p ) I(p) I ( p ) 已为假。从 2 p 2p 2 p 开始也正确,只是重复工作。
论证之所以能收拢,是因为循环一直运行到 p = s p=s p = s ,使 I ( P ) I(P) I ( P ) 覆盖所有不超过 s s s 的最小素因数。条件 p 2 < N p^2\lt N p 2 < N 恰好在 N = q 2 N=q^2 N = q 2 (q q q 为素数)时破坏这一点:循环在 P = q P=q P = q 停止,而 q 2 q^2 q 2 是 [ 2 , q 2 ] [2,q^2] [ 2 , q 2 ] 中唯一最小素因数为 q q q 的合数,于是保持未划去。执行期间,真只表示“尚未划去”;大于 s s s 的位置从不作为 p p p 检查,只由完备性一步认证。
例题详解
例题 9.1.5
(N = 49 N=49 N = 49 的完整过程)
这里 s = ⌊ 49 ⌋ = 7 s=\lfloor\sqrt{49}\rfloor=7 s = ⌊ 49 ⌋ = 7 。数组有 50 50 50 个单元,索引为 0 , … , 49 0,\dots,49 0 , … , 49 。
对 p = 7 p=7 p = 7 ,退出条件为 49 > 49 − 7 = 42 49\gt49-7=42 49 > 49 − 7 = 42 ,因此内层写入一次便退出,不会形成 56 56 56 。
处理 p = 7 p=7 p = 7 之前,未划去的数是所有素数以及 49 49 49 ;此时未划去不能证明它是素数。最终表为
2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47. 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47. 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47. 核对:新划去的数共 23 + 7 + 2 + 1 = 33 23+7+2+1=33 23 + 7 + 2 + 1 = 33 个。区间 [ 2 , 49 ] [2,49] [ 2 , 49 ] 有 48 48 48 个整数,其中 48 − 15 = 33 48-15=33 48 − 15 = 33 个是合数,与结果一致。
概念视角 组合
用容斥原理数幸存者 [ 1 , N ] [1,N] [ 1 , N ] 中不被任何素数 p ≤ N p\le\sqrt N p ≤ N 整除的整数,就是 1 1 1 和 ( N , N ] (\sqrt N,N] ( N , N ] 中的素数:除了用于筛的素数本身之外,正是筛法留下未标记的项。对用于筛的素数作容斥,可以不列出它们而数出个数:
# { m ≤ N : 对所有素数 p ≤ N , p ∤ m } = ∑ d ( − 1 ) k ( d ) ⌊ N d ⌋ , \#\{m\le N:\ \text{对所有素数 }p\le\sqrt N,\ p\nmid m\}=\sum_{d}(-1)^{k(d)}\left\lfloor\frac Nd\right\rfloor, # { m ≤ N : 对所有素数 p ≤ N , p ∤ m } = d ∑ ( − 1 ) k ( d ) ⌊ d N ⌋ , 其中 d d d 取遍不超过 N \sqrt N N 的不同素数之积(包括 d = 1 d=1 d = 1 ),k ( d ) k(d) k ( d ) 是这些素数的个数。N = 49 N=49 N = 49 时十六项之和为 12 12 12 :即整数 1 1 1 与从 11 11 11 到 47 47 47 的十一个素数。
取 N = 24 N=24 N = 24 。此时 s = 4 s=4 s = 4 ,循环处理 p = 2 , 3 , 4 p=2,3,4 p = 2 , 3 , 4 ;因 5 ≤ ⌊ 24 / 5 ⌋ = 4 5\le\lfloor24/5\rfloor=4 5 ≤ ⌊ 24/5 ⌋ = 4 不成立而停止。素数 5 5 5 未被用作筛选素数,却仍被正确报告。不超过 24 24 24 的合数没有最小素因数为 5 5 5 的,因为最小这样的数是 25 25 25 。输出为 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 2,3,5,7,11,13,17,19,23 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 。
取 N = 25 N=25 N = 25 ,测试 5 ≤ ⌊ 25 / 5 ⌋ = 5 5\le\lfloor25/5\rfloor=5 5 ≤ ⌊ 25/5 ⌋ = 5 成立,故 p = 5 p=5 p = 5 划去 25 25 25 。对 N = 26 N=26 N = 26 ,外层循环的值和筛选素数相同,且 2 2 2 还会划去 26 26 26 。
所需的筛选素数由 N N N 经由 s s s 决定,与输出中最大的素数无关。
例题 9.1.7
(单个输入 n = 10403 n=10403 n = 10403 )
假设只想判断 n = 10403 n=10403 n = 10403 是否为素数。因为 101 2 = 10201 ≤ 10403 < 10404 = 102 2 101^2=10201\le10403\lt10404=102^2 10 1 2 = 10201 ≤ 10403 < 10404 = 10 2 2 ,小素因数引理表明试除 d = 2 , … , 101 d=2,\dots,101 d = 2 , … , 101 就够了。
2 2 2 到 100 100 100 都不能整除 n n n ,而 d = 101 d=101 d = 101 能,因为 10403 = 101 ⋅ 103 10403=101\cdot103 10403 = 101 ⋅ 103 。这需要 100 100 100 次除法和常数个机器字的内存。
为了这一问题筛到 10403 10403 10403 要分配 10404 10404 10404 个单元。折中的办法是只筛到 101 101 101 ,再用不超过 101 101 101 的 26 26 26 个素数试除。
筛法旨在需要许多整数的答案时复用工作;实际何时划算取决于实现与工作负载。
代价
存储。 数组有 N + 1 N+1 N + 1 个布尔单元,即 O ( N ) O(N) O ( N ) ;另外只用常数个机器字,加上输出表。
时间。 初始化和最终扫描各需 N + 1 N+1 N + 1 步,外层循环至多执行 N \sqrt N N 次。剩余工作是划去操作,下面给出其上界。
当 N ≥ 4 N\ge4 N ≥ 4 ,执行 mark [ m ] : = false \texttt{mark}[m]:=\text{false} mark [ m ] := false 的次数至多为 1 2 N log 2 N \tfrac12N\log_2N 2 1 N log 2 N 。因此在机器字模型下,SIEVE ( N ) \operatorname{SIEVE}(N) SIEVE ( N ) 使用 O ( N log N ) O(N\log N) O ( N log N ) 步。
素数 p ≤ s p\le s p ≤ s 产生
⌊ N / p ⌋ − p + 1 ≤ N / p \left\lfloor N/p\right\rfloor-p+1\le N/p ⌊ N / p ⌋ − p + 1 ≤ N / p 次写入,因为 p ≥ 1 p\ge1 p ≥ 1 。对所有整数 2 ≤ p ≤ s 2\le p\le s 2 ≤ p ≤ s 求和只会增加项,故至多为 N ( H s − 1 ) N(H_s-1) N ( H s − 1 ) ,其中 H s = ∑ j = 1 s 1 / j H_s=\sum\limits_{j=1}^{s}1/j H s = j = 1 ∑ s 1/ j 。
下面证明 H s − 1 ≤ log 2 s H_s-1\le\log_2s H s − 1 ≤ log 2 s 。令 t = ⌊ log 2 s ⌋ t=\lfloor\log_2s\rfloor t = ⌊ log 2 s ⌋ ,则 2 t ≤ s 2^t\le s 2 t ≤ s 。对 k = 1 , … , t k=1,\dots,t k = 1 , … , t ,区块 2 k ≤ j < 2 k + 1 2^k\le j\lt2^{k+1} 2 k ≤ j < 2 k + 1 有 2 k 2^k 2 k 个整数,每项满足 1 / j ≤ 2 − k 1/j\le2^{-k} 1/ j ≤ 2 − k ,所以每块贡献至多 1 1 1 。这些完整区块覆盖 2 ≤ j ≤ s 2\le j\le s 2 ≤ j ≤ s ;最后一块可能延伸到 s s s 以外,加入其中额外的正项只会增大上界。因此 H s − 1 ≤ t ≤ log 2 s ≤ 1 2 log 2 N H_s-1\le t\le\log_2s\le\tfrac12\log_2N H s − 1 ≤ t ≤ log 2 s ≤ 2 1 log 2 N 。
当 N = 49 N=49 N = 49 ,实际有 43 43 43 次写入,而上界约为 137 137 137 。还存在形如 O ( N log log N ) O(N\log\log N) O ( N log log N ) 的更精细估计,但它依赖于此处未证明的素数倒数和的事实,本节没有依赖这一估计。
位复杂度。 数值与输入长度是不同的度量。对 N ≥ 2 N\ge2 N ≥ 2 ,令 b = ⌈ log 2 ( N + 1 ) ⌉ b=\lceil\log_2(N+1)\rceil b = ⌈ log 2 ( N + 1 )⌉ 。N + 1 N+1 N + 1 个数组单元随二进制输入长度 b b b 指数增长。若在位代价 RAM 中,带索引的数组访问和地址处理各耗至多 O ( b 2 ) O(b^2) O ( b 2 ) 次位运算,且 b b b 位整数的算术采用课本算法,包括乘法和除法各耗 O ( b 2 ) O(b^2) O ( b 2 ) 次位运算,则由前述字运算次数得到保守上界 O ( N log N b 2 ) = O ( N log 3 ( N + 2 ) ) O(N\log N\,b^2)=O(N\log^3(N+2)) O ( N log N b 2 ) = O ( N log 3 ( N + 2 )) 次位运算。这是上界,不是精确分析。紧凑存储的标记数组使用 N + 1 N+1 N + 1 位,常数个计数器需要 O ( b ) O(b) O ( b ) 位;另行存储的输出表需要额外空间。仅凭机器字代价模型无法推出这些位代价,这也不是单带图灵(Turing)机的上界。
其他方法。 对单个 n n n 试除至多需要 n \sqrt n n 次除法。对每个 n ≤ N n\le N n ≤ N 都试除至多需要 ∑ n ≤ N n ≤ N 3 / 2 \sum\limits_{n\le N}\sqrt n\le N^{3/2} n ≤ N ∑ n ≤ N 3/2 次除法。若改为对每个 d < n d\lt n d < n 试除,则代价为 O ( N 2 ) O(N^2) O ( N 2 ) 。这些初等上界大于筛法上界,但单凭比较上界不能确立所有输入的实际运行时间次序。
分段筛(可选思路)。 要列出 [ A , B ] [A,B] [ A , B ] 内的素数,其中 2 ≤ A ≤ B 2\le A\le B 2 ≤ A ≤ B :
先筛出不超过 ⌊ B ⌋ \lfloor\sqrt B\rfloor ⌊ B ⌋ 的基础素数;
再只为该窗口分配数组,对每个基础素数 p p p ,划去从 max ( p 2 , p ⌈ A / p ⌉ ) \max(p^2,p\lceil A/p\rceil) max ( p 2 , p ⌈ A / p ⌉) 到 B B B 的倍数。
正确性由小素因数引理和之前相同的论证得到。从 p 2 p^2 p 2 开始确保位于窗口内的基础素数不会被划去。对单个窗口,这可以比筛整个范围节省存储和工作;列举所有窗口时仍须处理每个窗口。
列举与素性检验不同
Miller–Rabin 等概率素性检验解决的是另一个问题。
输入。 测试处理单个 n n n ,它常有数百位;筛法输入上界 N N N ,处理每个 k ≤ N k\le N k ≤ N 。
代价。 测试运行时间为 log n \log n log n 的多项式;筛法的内存随数值 N N N 线性增长,对很大的 n n n 无法实际使用。
保证。 测试报告“合数”时,找到了可检验的证据;报告“可能为素数”时,依据的是测试分析给出的概率界,此处没有证明。该答案并非素性证明。由筛法正确性定理,筛法输出无需概率条件。
可检验的内容。 若记录划去 k k k 的素数,筛法关于 k k k 为合数的断言可用一次除法检验;关于 k k k 为素数的断言则依赖完备性论证:所有可能证明它为合数的素数都已使用。
确定性多项式时间素性检验也存在,但属于另一套理论。
反例模式
误解:未划去就一定是素数,或循环可以在 p 的平方小于 N 时停止 断言 A。 “一个位置在筛法中存活了一段时间,它就是素数。”
反例。 N = 49 N=49 N = 49 时,处理 p = 2 , 3 , 5 p=2,3,5 p = 2 , 3 , 5 之后,49 49 49 仍未划去,但 49 = 7 2 49=7^2 49 = 7 2 。
断言 B。 “条件 p 2 < N p^2\lt N p 2 < N 就足够。”
反例。 N = 25 N=25 N = 25 时,循环在 p = 5 p=5 p = 5 之前停止,25 25 25 被报告为素数。
诊断。 证明依靠最终不变量 I ( P ) I(P) I ( P ) ,而这要求 P 2 > N P^2\gt N P 2 > N 。
练习
快速检查
(对 N = 120 N=120 N = 120 和 N = 121 N=121 N = 121 ,列出实际使用的筛选素数。解释条件 p 2 < N p^2\lt N p 2 < N 会如何报告 121 121 121 。)
解答 10 2 = 100 ≤ 120 < 121 10^2=100\le120\lt121 1 0 2 = 100 ≤ 120 < 121 ,所以 N = 120 N=120 N = 120 时 s = 10 s=10 s = 10 。循环处理 p = 2 , … , 10 p=2,\dots,10 p = 2 , … , 10 ,筛选素数是 2 , 3 , 5 , 7 2,3,5,7 2 , 3 , 5 , 7 。
当 N = 121 N=121 N = 121 ,s = 11 s=11 s = 11 ,所以 p = 11 p=11 p = 11 也运行,且只划去 121 121 121 ,因为 121 > 121 − 11 121\gt121-11 121 > 121 − 11 使内层循环退出。
根据平方边界的讨论,121 = 11 2 121=11^2 121 = 1 1 2 是不超过 121 121 121 且最小素因数为 11 11 11 的唯一合数。严格不等式条件使循环在 p = 11 p=11 p = 11 处停止,故 121 121 121 留下并被误报为素数。
快速检查
(对 N = 50 N=50 N = 50 ,精确计算划去操作的写入次数;再数出 [ 2 , 50 ] [2,50] [ 2 , 50 ] 中的合数,并解释差异。)
解答 每个筛选素数 p p p 写入 ⌊ 50 / p ⌋ − p + 1 \lfloor50/p\rfloor-p+1 ⌊ 50/ p ⌋ − p + 1 次:
共 45 45 45 次。不超过 50 50 50 的素数有 15 15 15 个;[ 2 , 50 ] [2,50] [ 2 , 50 ] 有 49 49 49 个整数,故有 49 − 15 = 34 49-15=34 49 − 15 = 34 个合数。差值 45 − 34 = 11 45-34=11 45 − 34 = 11 是重复写入的次数。
再数被多个素数划去的数以作核对:
同时被 2 2 2 和 3 3 3 划去(从 9 9 9 开始):12 , 18 , 24 , 30 , 36 , 42 , 48 12,18,24,30,36,42,48 12 , 18 , 24 , 30 , 36 , 42 , 48 ,共 7 7 7 个;
被 2 2 2 和 5 5 5 划去:30 , 40 , 50 30,40,50 30 , 40 , 50 ;
被 3 3 3 和 5 5 5 划去:30 , 45 30,45 30 , 45 ;
被 2 , 3 , 5 2,3,5 2 , 3 , 5 都划去:只有 30 30 30 。
由容斥原理,划去的不同合数共有 45 − ( 7 + 3 + 2 ) + 1 = 34 45-(7+3+2)+1=34 45 − ( 7 + 3 + 2 ) + 1 = 34 个,与上面的计数一致。
快速检查
(比较两个数学变体:分别标记 [ 2 p , N ] [2p,N] [ 2 p , N ] 和 [ p 2 + p , N ] [p^2+p,N] [ p 2 + p , N ] 内 p p p 的全部倍数;若下端点超过 N N N ,视为区间为空。证明前者输出不变,后者有错,并找出出错的最小 N N N 。解释为什么直接修改上面先写入再检查的伪代码起点,不能安全实现第二个变体。)
解答 从 2 p 2p 2 p 开始,写入集合包含原来所有划去位置。额外写入的每个数都是 p j pj p j ,其中 j ≥ 2 j\ge2 j ≥ 2 ,所以都是合数。因此 (a)、(b) 仍成立,原有写入仍在,(c) 也成立;输出不变。
从 p 2 + p p^2+p p 2 + p 开始,p 2 p^2 p 2 不会被 p p p 划去。它的唯一素因数是 p p p ,故其他素数也不会划去它。N = 4 N=4 N = 4 时循环只处理 p = 2 p=2 p = 2 ,没有划去任何数,4 4 4 被误报为素数。N ≤ 3 N\le3 N ≤ 3 时没有合数,所以 N = 4 N=4 N = 4 是这个数学变体的最小失败输入。若直接把 p 2 + p p^2+p p 2 + p 代入上面先写入再检查的循环,情况更糟:N = 4 , p = 2 N=4,p=2 N = 4 , p = 2 时首先尝试写数组外的索引 6 6 6 。实现必须在写入之前检查起点,并且计算起点时不能溢出。
快速检查
(在字为 0 , … , 255 0,\dots,255 0 , … , 255 的 8 位机器上取 N = 255 N=255 N = 255 ,并假设无符号运算按模 256 256 256 回绕。分别做两个实验:只将带保护的外层测试改为“p ⋅ p ≤ N p\cdot p\le N p ⋅ p ≤ N ”,或只将带保护的内层更新改为“当 m ≤ N m\le N m ≤ N 时令 m : = m + p m:=m+p m := m + p ”;另一部分保持有保护。说明每个实验会出什么问题,再检查完全带保护的版本。)
解答 使用朴素内层循环且 p = 2 p=2 p = 2 时,m = 254 m=254 m = 254 加一步得到 256 ≡ 0 256\equiv0 256 ≡ 0 。因为 0 ≤ 255 0\le255 0 ≤ 255 ,循环永不结束。
使用朴素条件时,p = 16 p=16 p = 16 得到 256 ≡ 0 ≤ 255 256\equiv0\le255 256 ≡ 0 ≤ 255 ,循环继续。接着 p = 17 p=17 p = 17 得到 289 ≡ 33 289\equiv33 289 ≡ 33 。因为 mark [ 17 ] \texttt{mark}[17] mark [ 17 ] 为真,内层从 33 33 33 开始划去 33 , 50 , 67 , … 33,50,67,\dots 33 , 50 , 67 , … 。但 67 67 67 是素数,其数组位置被错误标为合数;溢出后的循环甚至不一定终止。
带保护的版本检查 16 ≤ ⌊ 255 / 16 ⌋ = 15 16\le\lfloor255/16\rfloor=15 16 ≤ ⌊ 255/16 ⌋ = 15 ,条件不成立,故在 s = 15 s=15 s = 15 正确停止。
另有长度问题:N + 1 = 256 N+1=256 N + 1 = 256 不能放进 8 位字。若分配接口无法表示该长度,前提失败,过程必须拒绝;若长度使用更宽类型且 L ≥ 256 L\ge256 L ≥ 256 ,所述前提允许 N = 255 N=255 N = 255 ,此时带保护的字运算安全。两种情形均不能让溢出的长度悄悄回绕。
快速检查
(解释为什么筛到 N = 10 12 N=10^{12} N = 1 0 12 与对一个 n ≈ 10 12 n\approx10^{12} n ≈ 1 0 12 运行概率检验,即使都说“素数”,答案的性质也不同。)
解答 筛法需要 10 12 + 1 10^{12}+1 1 0 12 + 1 个单元,可能超过分配上限 L L L 。若能运行,筛法正确性定理证明每个 k ≤ N k\le N k ≤ N 的状态。
概率检验只处理一个 n n n ,其代价是约 40 40 40 位输入长度的多项式。“可能为素数”的答案带有误差界,而不是证明。
两者回答的问题和保证不同:筛法有证明地回答“哪些 k ≤ N k\le N k ≤ N 是素数”;测试以高置信度回答“这个 n n n 是否为素数”。
相关笔记
先修知识包括整除、强归纳法(用于对 p p p 的归纳)和素因数分解(用于保证 lpf \operatorname{lpf} lpf 存在)。自然的后续主题包括最小素因数筛,以及利用筛出的素数表试除。