如果许多查询要求分解同一范围内整数的质因子,反复试除会重复做很多工作。我们可以先记录这个范围内每个整数的最小质因子,再对每个查询反复查表并除去一个质因子。
这里的筛法称为线性筛,是因为生成的合数总次数与上限呈线性关系。嵌套循环不一定意味着二次复杂度:关键是循环实际访问了多少个数对。我们将为每个合数指定唯一的生成数对,并证明停止规则保留了这种对应关系。
定义表中各项的含义
定义 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 如何被分类 |
|---|---|---|
| 到达时未标记:素数 | ||
| 到达时未标记:素数 | ||
| 由 生成 | ||
| 到达时未标记:素数 | ||
| 由 生成 | ||
| 到达时未标记:素数 | ||
| 由 生成 | ||
| 由 生成 | ||
| 由 生成 | ||
| 到达时未标记:素数 | ||
| 由 生成 |
当 时,素数 2 生成 6,素数 3 生成 9。当 时,最小质因子是二,因而不允许用素数 3 生成 12。12 的标准数对 会稍后出现,但仍早于外层下标 12。
反例模式
每次只处理第一个素数可能将九错误分类
假设改动后的循环每生成第一个乘积就停止。当 时,它用素数 2 生成 6,却永远到不了用于生成 9 的素数 3。
9 唯一可能的允许标准数对是 。如果漏掉它,到达 9 时它仍未标记,就会被错误地作为素数加入列表。合数外层下标的循环常常在其最小质因子处停止,但这不意味着每个外层下标都应在第一个素数之后停止。
第一个例子拿走一次迭代;第二个例子拿走一项限制。
反例模式
去掉因子限制破坏唯一性,但不自动证明最终值都错误
若允许大于 spf[i] 的素数,12 可以由 生成,又由 生成。第一次写入三,尽管最小质因子是二。
后一次写入可能修正这个值,因此仅凭此例不能证明修改后算法的最终表错误。但它确实说明每个合数只生成一次的论证不再适用。不同的循环需要自己的正确性和复杂度分析,不能因为代码相似就沿用线性界。
先建表,再沿因子链接分解
输入以整数为类型前提。构造函数检查 ;因子提取函数检查参数在一与表的上限之间。它假定所给表是构造后未被修改的正确 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) 返回上表中的最小质因子,0 和 1 处是标记项,并返回素数列表 [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
它输出 个二,达到因子数量的对数界。这并不能消除建表至 所需的 预处理及存储项成本。输出大小和为所有可能的有界查询做准备的成本必须分别衡量。