動機
為甚麼要列出質數?
許多計算需要列出不超過上界 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 存在)。自然的後續主題包括最小質因數篩,以及利用篩出的質數表試除。