跳转至

筛法：从埃氏筛到 Brun

层级：① 方法论共识 · 来源：Eratosthenes (公元前 3 世纪) / Brun (1919) / Selberg (1947)

一句话版本

筛法是数论的"显微镜"：用小素数去筛掉合数，剩下的结构就是素数分布的信息。 它是 2000 年来研究素数问题的第一武器，也是所有未解猜想的战场。

三个里程碑

1. 埃拉托色尼筛（公元前 3 世纪）

最朴素的筛：把 2 的倍数划掉，再划 3 的倍数……复杂度 \(O(n\log\log n)\)，至今仍是生成素数表最快的实用方法。

2. Legendre / Brun 组合筛（1896 / 1919）

埃氏筛"筛到底"代价太大。Legendre 的想法：只筛前 \(a\) 个素数，用容斥公式估计剩下的。Brun (1919) 把容斥换成上下界夹逼（截断的容斥级数），一举证明了孪生素数倒数和收敛——筛法第一次攻克了以前完全碰不到的问题。

3. Selberg 筛（1947）

用二次型加权，把上界筛推到当时最优。现代的 Selberg–Brun 框架给出孪生素数对的上界估计：

\[\pi_2(x) \lesssim \frac{8C_2\, x}{\ln^2 x} \cdot (\text{常数因子})\]

注意是上界——筛法天然给不出精确主项，这就是下面的 parity 问题。

筛法的天花板：奇偶性壁垒（parity problem）

筛法在原则上无法区分"有奇数个素因子"与"有偶数个素因子"的数。而"恰好是素数"正是奇偶性信息最极端的情形。这就是为什么：

  • 孪生素数猜想的精确主项 \(2C_2 x/\ln^2 x\) 至今只是猜想；
  • 哥德巴赫、孪生素数这类"短窗内至少命中一次"的问题，全都卡在同一个壁垒上。

哥德巴赫、孪生素数这类「短窗内至少命中一次」的问题，全都卡在同一个壁垒上。

自己验证

# 埃氏筛 = 最快的素数生成器：验证与素数定理词条一致
def primes_upto(n):
    sieve = bytearray([1]) * (n + 1)
    sieve[0:2] = b"\x00\x00"
    for p in range(2, int(n**0.5) + 1):
        if sieve[p]:
            sieve[p*p::p] = bytearray(len(sieve[p*p::p]))
    return sieve

S = primes_upto(1_000_000)
assert sum(S) == 78498  # pi(10^6)
print("埃氏筛 pi(10^6) = 78498 ✓")

延伸

发布：2026-10-23 07:39:14 · 数论库