若很多查詢都要求同一上限內整數的質因數,每次重新試除會重複工作。我們可以先記錄範圍內每個整數的最小質因數,再對每個查詢反覆查表、除去一個質數。
這裏的篩法稱為線性,是因為生成合成數的總次數與上限呈線性關係。巢狀迴圈不自動代表平方時間;真正要問的是迴圈共訪問了多少對。我們會把每個合成數分配給唯一生成配對,並證明停止規則保留這個分配。
定義每個表格項目的含義
定義 17.2.1
(最小質因數與標記項目)
質數是大於一、正因數只有一和自身的整數。對 ,設 是其最小質因數。這樣的因數必存在:最小的大於一因數必為質數,否則它某個更小因數也會整除 。
對整數上限 ,表格下標是 。建立後, 時 spf[x] 就是 。零、一的位置保留零作標記,並不是說零是它們的質因數。一的質因數串列為空。
建立期間,下標至少為二的零表示「尚未標記」。只有外層迴圈到達該位置,而且正確性不變量支持時,才可解讀為質數,不能把初始所有零項都當成質數。
由已處理整數與質數生成合成數
按遞增次序處理 ,維持已發現質數的遞增串列。若 spf[i] 仍為零,就設為 ,並把 加到質數串列。然後按遞增次序訪問質數 ,生成 ,但只在以下條件成立時繼續:
每個獲准配對都設定 spf[i*p] = p。第一項限制是唯一生成證明的關鍵,第二項保證不超預處理範圍。實作在形成乘積前檢查 p > N // i,連不需要的超大乘積也毋須先算出來。
定理 17.2.2
(篩法的唯一生成與完整性)
設 。在上述構造中:
- 迴圈寫入的每個配對 都滿足 ,而且 是合成數;
- 每個合成數 恰好被寫入一次,所用配對是 ;
- 外層到達下標 時, 仍未標記,當且僅當 是質數。
因此最後 的 spf[x] 都等於 ,質數串列恰好按遞增次序包含 以內的全部質數。
證明
(最小因數、標準配對與質數測試)
命題 1。 對獲准配對, 的每個質因數都至少為 。 本身是質數並整除 ,所以 是 的最小質因數;又因 , 是合成數。
命題 2 的唯一性。 若同一合成數 由兩個獲准配對生成,由命題 1,兩者的質數部分都等於 ,另一部分也都等於 ,兩個配對完全相同。沒有合成數會被寫入兩次。
命題 2 的存在性,連同命題 3。 對外層下標作歸納。設 ,並假設迴圈到達 時,所有小於 的下標都已正確分類,spf 中的值也正確。若 是合成數,令 ,,則 。小於 的質數不能整除 ,否則也會整除 ;所以 。因此質數 已在串列中,或者 且剛被加入。內層迴圈中先於 的每個質數也滿足因數限制,乘積至多為 ,所以兩個停止條件都不會令迴圈到不了 。這個配對在較小的下標 就寫入了 ,早於迴圈到達 。若 是質數,由命題 1,它不會被寫入,因為每個被寫入的下標都是合成數。所以到達 時它仍未標記,被加入串列並得到 。由二開始歸納,便完成整張表。∎
證明透視
篩法證明中兩個限制各有甚麼作用
因數限制 有兩個方向相反的作用。順著看,它使 成為 的最小質因數,所以每次寫入的值都正確,也沒有合成數會被第二個配對到達。倒過來看,標準配對 必定滿足它,所以沒有任何合成數被漏掉。界限 在兩個作用中都不起作用;它只使寫入留在表格之內,證明中只對 檢查一次。
不顯而易見的一步,是歸納沿外層下標進行,並用到 :合成數的餘因數必定在合成數本身之前處理。這個次序正是質數測試不需要另外證明的原因。輪到某數時仍未標記,表示沒有標準配對還未到達,所以它是質數。證明的前半保證每次寫入正確而且唯一;只有後半才說明沒有合成數被漏掉。
在小上限追蹤整張表
例題 17.2.3
(十二以內每個合成數都有唯一生成配對)
對 ,建立結果如下:
| x | 最小質因數 | x 如何分類 |
|---|---|---|
| 到達時未標記:質數 | ||
| 到達時未標記:質數 | ||
| 由 生成 | ||
| 到達時未標記:質數 | ||
| 由 生成 | ||
| 到達時未標記:質數 | ||
| 由 生成 | ||
| 由 生成 | ||
| 由 生成 | ||
| 到達時未標記:質數 | ||
| 由 生成 |
在 ,質數二生成六,質數三生成九。在 ,最小因數是二,所以不容許質數三生成十二。十二的標準配對稍後以 出現,仍然在外層下標十二之前。
反例模式
每次只處理一個質數,會把九分類錯誤
假設修改後的迴圈總是在第一個生成乘積後停止。在 ,它用質數二生成六,然後不再到質數三生成九。
九唯一獲准的標準配對是 。若漏掉它,到達九時仍未標記,就會錯誤地把九加入質數串列。合成外層下標常在自己的最小質數停止,卻不代表每個外層下標都應在第一個質數後停止。
第一個例子拿走一次迭代;第二個例子拿走一項限制。
反例模式
移除因數限制破壞唯一性,卻不自動證明所有最終值都錯
若容許大於 spf[i] 的質數,十二可在 生成,再在 生成。第一次賦值用三,雖然最小因數其實是二。
較後賦值可能修正它,所以這個例子本身不證明改動後算法的最終表一定錯。它確實證明每個合成數只生成一次的論證已不適用。不同迴圈要有自己的正確性與複雜度分析,不能因程式相似就繼承線性界限。
建表後,沿因數連結前進
輸入以前提要求為整數。建立函數檢查 ;提取函數檢查參數介乎一與表格上限。提取假設表格是建立所得、未經改動的正確 SPF 表,不會重新驗證任意傳入項目。
def smallest_prime_factors(limit):
if limit < 1:
raise ValueError("the limit must be at least one")
spf = [0] * (limit + 1)
primes = []
for value in range(2, limit + 1):
if spf[value] == 0:
spf[value] = value
primes.append(value)
for prime in primes:
if prime > spf[value] or prime > limit // value:
break
spf[value * prime] = prime
return spf, primes
def factorize_from_spf(value, spf):
if not 1 <= value < len(spf):
raise ValueError("the value must lie between one and the table limit")
factors = []
while value > 1:
prime = spf[value]
factors.append(prime)
value //= prime
return factors
smallest_prime_factors(12) 回傳表中因數,零、一保留標記,另回傳質數串列 [2,3,5,7,11]。上限一也合法,得到 [0,0] 及空質數串列。若先建至 100,再調用 factorize_from_spf(84, spf),便得到 [2,2,3,7]。
證明因數提取的結果
命題 17.2.4
(以重複查表提取因數)
設 spf 是上限 以內的正確表,。則 factorize_from_spf(x, spf) 回傳一個非遞減的質數串列,其乘積為 。每項輸出對應一次查表和一次精確除法,串列至多有 項。
證明
(關於目前商的不變量)
設目前商為 ,已輸出串列為 , 是其中第 項。維持
初始空乘積為一,。當 ,表格提供整除 的質數 。把 加入串列,再把 改為 ,保留等式。因為 ,商嚴格減小,所以迴圈在 時終止,此時已輸出質數的乘積恰好為 。
串列非遞減。若比剛選的最小因數 更小的質數整除下一個商 ,它也會整除 ,與 的最小性矛盾。同一質數重複出現,記錄它的重數。
若輸出 項,每項至少為二,所以 ,。一有 ; 則輸出 個二,恰好達到界限。∎
例題 17.2.5
(分解八十四,保留可檢查的乘積見證)
連續的商為 ,輸出因數為 ,乘積是 。把相同因數分組,可寫成緊湊形式 。
商為 21 時,下一個查表值是三,而不是二。表格用目前商作下標,不能每次讀取原輸入位置。一回傳空串列,因為空乘積為一;零則不在此提取條件內。
例題 17.2.6
(邊界上限與質數查詢)
對 ,外層 range(2, 2) 是空的,所以構造回傳 [0,0] 及空質數串列;分解一則回傳 []。對 ,迴圈到達 時 spf[2] 為零,把它設為二並加入二。內層迴圈檢查質數二: 為假,但 為真,所以停止。結果是 [0,0,2] 及質數串列 [2]。在上限為 的表中查詢 ,得到 spf[97] 等於 ,輸出 ,商變為一:質數回傳只有一項的串列。
常見錯誤
(把每個零項都當作質數)
建表期間,下標至少為二而值仍為零,只表示尚未標記。外層迴圈剛開始處理 時, 的項目仍為零,雖然 是合成數;它在同一次迭代中才由配對 寫入。只有當外層迴圈本身到達該下標時,才可把零讀作「質數」,因為那時它的標準配對已經輪過。
常見錯誤
(查原輸入而不是目前的商)
假設提取時除掉商,卻一直讀取 spf[84]。在商為 時輸出二,在 時再輸出二,在 時又輸出二,但二並不整除 ,21 // 2 無聲地截為 。迴圈接著在 、 和 時繼續輸出二,最後共輸出六個二,其積為 ,不是 。查表必須用目前的商,如上面的不變量所要求。
解釋巢狀建立過程為甚麼是線性
每次成功內層迭代寫入一個合成數。唯一生成證明把成功次數限制為上限內的合成數數量,因此不超過 。每次外層迭代,另外最多有一次終止的失敗檢查,因為它隨即跳出。質數判定與外層開銷也只有 次。
概念視角組合
把篩法看成整數上的一棵樹
把每個 與 相連,由於父節點較小,這是 上以 為根的樹。 的子節點是所有乘積 ,其中 為質數且 ( 時可取任何質數),而對 ,篩法在迴圈到達 時恰好寫下這些邊;由 出發的邊通往各質數,即迴圈到達時仍未標記的下標。 個頂點的樹有 條邊,這就是線性的計數。因數提取是從 沿樹向上走到根,邊上的標記就是輸出的質因數。
所以,假設一般常數字長存取與質數串列的攤銷常數加入模型,預處理需要 次算術、陣列操作。證明不需要估算質數數量或質數倒數和,只把工作計入標準合成數寫入及終止檢查。
SPF 陣列與質數串列合共使用 個儲存項目,即使很多位置是合成數也一樣。這是單元界限,不是 位元聲稱;儲存整數各可能需 位元。若不把整數當作機器字,除法、乘法和比較也有位元成本。Python 整數保留精確運算;固定位元版本則須讓下標及計算具有適當範圍。以除法作乘積防護,可先拒絕越界乘積而毋須算出它。
預處理後,每個輸出因數只需一次查表與精確除法,另加常數開銷。對查詢 ,共作 次這類操作,並輸出 個質數項目。寫出二進位整數還有輸出位元成本,串列操作界限不會消除它。
只為一個查詢,把每個整數預處理至巨大上限,未必值得。不論實際查詢多少值,稠密表的時間與記憶體都隨上限增長。它的長處是讓多個有界查詢共用這些工作。其他工作量需要不同選擇與分析,本節不聲稱這是通用最佳分解方法。
練習與詳解
快速檢查
(1. 解釋九為甚麼在訪問前已被標記)
上限十二時,哪個外層值與質數生成九?為甚麼每次總在第一個質數後停止會失敗?
解答 · 解答 1
外層值三與質數三生成九。該外層值先由質數二生成六,但因 spf[3] 為三,質數三也獲准。若第一個質數後停止,九會未經標記,稍後被錯當質數。
快速檢查
(2. 辨認標準配對,而不是任意因數配對)
為甚麼線性篩以 生成十二,並拒絕 ?容許兩個配對,是否本身足以證明改動後算法的最終表一定錯?
解答 · 解答 2
二是十二最小質因數,標準商便是六。外層值四的 spf[4] 為二,質數三超出獲准界限。容許兩者會失去唯一生成,較後的二賦值可能修正較早的三。改動方法的最終值與時間,都要另作證明。
快速檢查
(3. 按迴圈不變量檢查因數串列)
每步使用目前商來分解八十四,列出全部商、因數串列與乘積見證。商為 21 時,為甚麼不應再次取二?
解答 · 解答 3
商為 ,因數是 ,乘積為 84。每步已輸出乘積乘目前商都等於 84。21 的查表值是三,二不整除 21;重複讀原項目會破壞不變量。
快速檢查
(4. 說清楚標記值代表甚麼)
一的因數提取回傳甚麼?spf[1] = 0 是否聲稱零是質數?若調用者直接提供一張表,而不是當場建立,需要哪些假設?
解答 · 解答 4
一回傳 [],代表空乘積。零只是在零、一位置的標記,不是質數。提取要求未經改動的正確 SPF 表,以及範圍內整數查詢,不會證明任意傳入項目正確。零、負查詢、超過上限的查詢都會拒絕。
快速檢查
(5. 計入所有內層迭代與正確的儲存單位)
巢狀迴圈為甚麼仍只需線性機器字操作?停止而未生成合成數的迭代如何計算?為甚麼 項不自動等於 位元?
解答 · 解答 5
每次成功迭代屬於不同合成數,所以至多 次。每次外層最多有一次終止失敗檢查,另加 。儲存整數各可能需 位元,所以線性項目數不同於線性位元空間。算術成本也取決於數值模型。
快速檢查
(6. 把查詢輸出長度與預處理選擇分開)
查詢 會輸出多少個因數?若只需一個很大的 x,這個短輸出界限是否支持建立至 x 的整張表?
解答 · 解答 6
輸出 個二,達到對數因數數量界限。但這沒有消除稠密表建立至 的 預處理與儲存項目成本。輸出大小與準備所有可能有界查詢的成本,必須分開評估。