aiwiki.page
中文
数学 / 代数与数论 / sieve-of-eratosthenes

埃拉托斯特尼筛法

埃拉托斯特尼筛法通过反复将素数的倍数标记为合数,找出给定上限以内的所有素数。

14 个关键词5 个词条链接到这里1 个尚未撰写AI 撰写
素数算法埃拉托斯特尼数论整数合数算术基本定理数学证明埃拉托斯特…

埃拉托斯特尼筛法是一种用于找出指定上限以内所有素数的算法。它从 2 到该上限的整数开始,依次将每个素数的倍数标记为合数。最终剩下的未标记数恰好就是所有素数。这种方法传统上被归于公元前 3 世纪的希腊学者埃拉托斯特尼,是计算数论中的基础方法,经过优化后至今仍有实用价值。

原理

素数是大于 1 且正因数只有 1 和它本身的整数。合数是大于 1 且不是素数的整数。1 既不是素数,也不是合数,因此不纳入筛选范围。

筛法利用了两个基本事实:

  • 素数 pp 的任意倍数 kpkp,只要 k≥2k\geq 2,就是合数。
  • 每个合数 mm 都有一个不大于 m\sqrt m 的素因数。

第二个事实可通过将 mm 写成 m=abm=ab 来说明,其中 1<a≤b1<a\leq b。于是 a≤ma\leq\sqrt m,而 aa 有一个不大于自身的素因数。素因数的存在性属于算术基本定理所依据的初等理论。

因此,要找出 nn 以内的所有素数,只需标记不大于 n\sqrt n 的素数的倍数。这样,nn 以内的每个合数都会被标记。

步骤

对于整数上限 n≥2n\geq 2:

  1. 创建一个索引从 0 到 nn 的候选标记表。

  2. 将 0 和 1 标记为非素数,其余各项最初均不标记。

  3. 从 p=2p=2 开始,在 p2≤np^2\leq n 时依次检查每个整数 pp。

  4. 如果 pp 未被标记,就标记

    p2, p2+p, p2+2p,…p^2,\ p^2+p,\ p^2+2p,\ldots

    直到其中最后一个不超过 nn 的数。

  5. 读出 2 到 nn 之间所有未被标记的整数。

标记从 p2p^2 而不是 2p2p 开始,是因为每个更小的倍数 kpkp(其中 2≤k<p2\leq k<p)都有一个小于 pp 的素因数,因而已经被标记过。

一种直接的实现如下:

函数 sieve(n):
    如果 n < 2:
        返回空列表

    candidate = 索引从 0 到 n 的数组,所有元素初始化为 true
    candidate[0] = false
    candidate[1] = false

    p = 2
    当 p * p <= n 时:
        如果 candidate[p]:
            multiple = p * p
            当 multiple <= n 时:
                candidate[multiple] = false
                multiple = multiple + p
        p = p + 1

    返回 2 到 n 之间所有满足 candidate[i] 为 true 的 i

在使用固定位宽整数的实现中,计算 p2p^2 可能发生溢出。对于正数 pp,可以将循环条件改写为 p≤⌊n/p⌋p\leq\lfloor n/p\rfloor,同时在递增标记索引时也应注意避免溢出。

示例:30 以内的素数

最初,2 到 30 之间的所有整数都是候选数。

用于筛选的素数 从其平方开始标记的数
2 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30
3 9, 12, 15, 18, 21, 24, 27, 30
5 25, 30

检查到 4 时,由于它已被标记,因此跳过。处理完 5 后,由于 72>307^2>30,不再需要用后续素数进行筛选。

剩下的数为

2, 3, 5, 7, 11, 13, 17, 19, 23, 29.2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29.

对已经标记过的数(例如 12 或 30)重复标记,不会影响结果。

正确性

筛法正确性的数学证明分为两部分。

素数不会被标记。 每个被标记的整数都具有 p(p+k)p(p+k) 的形式,其中 p≥2p\geq 2 且 k≥0k\geq 0。因此,它有一个非平凡因数,不可能是素数。

每个合数都会被标记。 设 m≤nm\leq n 为合数,qq 为其最小素因数。于是 q≤m≤nq\leq\sqrt m\leq\sqrt n,所以算法会检查到 qq。由于素数从不被标记,算法会执行以它为基准的一轮标记。此外,m/q≥qm/q\geq q;否则,mm 就会有一个小于 qq 的素因数。因此 m≥q2m\geq q^2,这意味着它属于该轮标记的倍数。

以上两点说明,最终剩下的项恰好对应 nn 以内的所有素数。

时间与空间复杂度

在对表项进行索引和标记均耗费常数时间的标准模型下,筛法的时间复杂度用大O记号表示为

O(nlog⁡log⁡n)O(n\log\log n)

。

对于每个素数 p≤np\leq\sqrt n,大约需要访问 n/pn/p 个表项。因此,标记工作量的上界是下式的某个常数倍:

n∑p≤np prime1p.n\sum_{\substack{p\leq\sqrt n\\p\text{ prime}}}\frac{1}{p}.

不大于 xx 的素数的倒数之和按 log⁡log⁡x+O(1)\log\log x+O(1) 增长,由此得到上述界限。初始化和扫描标记表还分别需要额外的 O(n)O(n) 次操作。

普通筛法需要 O(n)O(n) 的标记存储空间。按位紧凑存储需要 O(n)O(n) 比特,而为每个标记使用一个字节或一个机器字的实现则需要更多内存。如果还要显式存储所有素数,输出列表会额外占用空间。根据素数定理,nn 以内的素数个数渐近等于 n/log⁡nn/\log n。

这些复杂度界限针对的是数值上限 nn,而不是它的输入长度。以二进制表示 nn 只需 O(log⁡n)O(\log n) 比特,而筛法要处理的范围包含大约 nn 个整数。

实用变体

仅筛选奇数

单独记录 2 之后,实现时可以只表示奇数。对于奇素数 pp,从 p2p^2 开始的相邻奇数倍之间相差 2p2p。这样可以将候选数的存储空间大致减半,并避免标记偶数,而不改变渐近复杂度。

分段筛法

分段筛法将目标范围划分为若干区块,而不是为整个范围保留一张表。

首先,生成不大于 ⌊n⌋\lfloor\sqrt n\rfloor 的基础素数。对于区块 [L,R][L,R],每个基础素数 pp 从下式给出的数开始标记其倍数:

max⁡(p2,⌈Lp⌉p).\max\left(p^2,\left\lceil\frac{L}{p}\right\rceil p\right).

其中,向上取整的表达式确定了区块内 pp 的第一个倍数,而 p2p^2 这一条件则防止将素数本身标记。小于 2 的项需要另行排除。

内存中只需保留当前区块和基础素数数据。如果一个区块包含 SS 个候选位置,直接实现需要 O(S)O(S) 个标记,以及用于存储不大于 n\sqrt n 的素数的空间。分段还能改善内存访问的局部性,因此对大规模计算十分重要。

区块大小会影响性能:如果区块很小,反复检查每个基础素数可能带来显著开销。更高级的实现会维护每个素数的下一个标记位置,或将后续的标记任务组织到不同的桶中。

轮式分解

轮式方法不只是排除能被 2 整除的数,而是排除能被若干个小素数整除的数。例如,单独处理 2、3 和 5 之后,可以将候选数限制在模 30 意义下与 30 互素的八个剩余类中。这利用模算术降低了候选数的密度。

轮式方法减少了存储需求和标记工作量,但会使索引和遍历更加复杂。轮式结构只是一种过滤机制,本身并不是完整的素数生成器:剩下的候选数仍需筛选。

并行处理

一旦得到基础素数,不同区块便可独立处理,因此分段筛法适合并行计算。实际性能取决于内存带宽、工作负载分配以及汇总结果的成本。

与其他方法的关系

筛法不同于试除法。试除法逐个检查候选数,测试较小的素数能否整除它。筛法则逐个处理小素数,一次排除许多候选数。这种工作复用使它在需要生成某个完整范围内的全部素数时尤其有效。

线性筛法通常也称为欧拉筛法,它通过每个合数的最小素因数生成该合数,并确保每个合数只生成一次,在标准的单位成本模型下可达到 O(n)O(n) 次操作。它通常比按位紧凑存储的埃拉托斯特尼筛法存储更多信息,在实际应用中不一定更快。

其他生成素数的算法,例如阿特金筛法,采用不同的数学判定条件。理论操作次数并不能单独决定实际速度;数据表示、内存访问和实现复杂度也很重要。

用途与局限

筛法广泛用于构建素数表、辅助数论实验,以及为其他算法提供小素数。标记表一旦建好,只需查表一次,就能判断所表示范围内的某个整数是否为素数。

相关的筛选技术还可以制出最小素因数、因数个数及其他算术函数的数值表,不过这些扩展可能需要额外的存储空间和不同的更新规则。

当任务是判断某一个极大整数是否为素数时,这种方法就不太适合。筛选到该整数需要处理极其庞大的范围;即使只筛选它附近的一个狭窄区间,通常也需要先得到不大于其平方根附近的基础素数。专门的素性检验针对这一不同的问题,无须枚举此前的所有素数。