素数计数函数记作 π(x),表示小于或等于实数 x 的素数的个数。即
π(x)=#{p:p is prime and p≤x},
其中,# 表示有限集合中元素的个数。例如,π(10)=4,因为不超过 10 的素数是 2,3,5, 和 7。素数计数函数是数论的核心研究对象之一:其精确值描述素数的分布,而其近似式及误差项则将素数与数学分析和黎曼ζ函数联系起来。
定义与基本性质
这一定义适用于所有实数 x,且当 x<2 时,π(x)=0。由于素数都是整数,
π(x)=π(⌊x⌋).
该函数单调不减且右连续。它在相邻两个素数之间保持常数,并在每个素数处发生大小为 1 的跳跃。
利用示性函数,可将其写为
π(x)=1≤n≤x∑1P(n),
其中,当 n 为素数时,1P(n) 等于 1,否则等于 0。特别地,对每个整数 n≥2,都有
π(n)−π(n−1)={1,0,n is prime,n is composite.
以下是一些精确值:
| x |
π(x) |
| 10 |
4 |
| 100 |
25 |
| 1,000 |
168 |
| 10,000 |
1,229 |
| 100,000 |
9,592 |
| 1,000,000 |
78,498 |
| 1,000,000,000 |
50,847,534 |
这里使用符号 π 只是一种惯例,并不表示圆周率。
渐近分布
素数定理
最基本的近似由素数定理给出:
π(x)∼logxx(x→∞),
其中,log 为自然对数。符号 ∼ 表示
x→∞limx/logxπ(x)=1.
这一结论描述的是相对误差,并不意味着两者精确相等,也不意味着两者之差的绝对值有界。随着 x 增大,近似值的相对误差越来越小,但绝对误差未必会减小。
由此可得
xπ(x)⟶0.
因此,尽管素数有无穷多个,它们在正整数中的自然密度仍为零。
该定理还启发了一种直观估计:在很大的数值 x 附近,一个整数为素数的概率约为 1/logx。这是对局部密度的近似,并不是说各个整数是否为素数构成了一系列相互独立的随机事件。整除关系和同余限制赋予了素数分布很强的算术结构。
对数积分
通常更为精确的近似是对数积分
li(x)=PV∫0xlogtdt,x>1.
这里,PV 表示柯西主值;由于被积函数在 t=1 处有奇点,需要采用这一概念。另一种常见约定使用
Li(x)=∫2xlogtdt.
这两个函数相差一个常数。
反复使用分部积分法可得渐近展开
li(x)∼logxx(1+logx1+(logx)22!+(logx)33!+⋯).
这是一个渐近级数,而不是对固定的有限 x 收敛的展开式。当 x 趋于无穷大时,保留固定项数、逐次增加所保留的项,可以得到越来越精细的渐近描述。
素数定理也可以等价地表述为
π(x)∼li(x).
误差项与黎曼猜想
差值
E(x)=π(x)−li(x)
衡量精确计数与其主要光滑近似之间的偏差。
一个经典的无条件估计指出,存在常数 c>0,使得
π(x)=li(x)+O(xe−clogx).
大O记号表示,当变量充分大时,相应量的大小不超过所给表达式的某个常数倍。目前已有更强的无条件估计,但这一形式已经比基本的素数定理精确得多。
黎曼猜想等价于估计式
π(x)=li(x)+O(xlogx)(x→∞).
这将关于一个复值函数零点的断言,与素数分布不规则程度的定量界联系了起来。
尽管在已计算的极大范围内,li(x) 始终大于 π(x),但它并不是对所有 x 都成立的上界。利特尔伍德于1914年证明,
π(x)−li(x)
会无穷多次改变符号。因此,在很大的有限范围内观察到某个不等式成立,并不足以证明它在全局成立。
加权计数函数与ζ函数的零点
在解析数论中,加权素数计数往往比直接研究 π(x) 更容易处理。两个切比雪夫函数分别是
ϑ(x)=p≤x∑logp
和
ψ(x)=pk≤x∑logp,
其中,p 遍历素数,k 遍历正整数。第二个函数对素数幂进行计数,并赋予 p 的每个幂以权重 logp。
素数定理与以下两个命题中的任意一个等价:
ϑ(x)∼x,ψ(x)∼x.
分部求和给出精确关系
π(x)=logxϑ(x)+∫2xt(logt)2ϑ(t)dt,x≥2.
另一个有用的函数是黎曼的加权素数幂计数函数:
J(x)=pk≤x∑k1.
它满足
J(x)=k≥1∑k1π(x1/k).
对于固定的 x,只有有限项不为零。利用莫比乌斯函数 μ,可以反演这一关系:
π(x)=k≥1∑kμ(k)J(x1/k).
黎曼显式公式将 J(x) 的一种修正版表示为对数积分、ζ函数非平凡零点的贡献以及其他修正项之和。零点的贡献解释了计数函数围绕光滑近似的振荡。在素数幂处,要使显式公式精确成立,就需要约定间断点处的取值,通常取跳跃两侧函数值的中点。
这些恒等式在素数计数与复分析之间架起了桥梁;将它们用于数值计算时,需要谨慎截断并控制误差。
精确计算
筛法
最直接的系统性方法是埃拉托斯特尼筛法。它标记给定上界以内的合数,然后统计大于 1 且未被标记的整数。
标准实现需要 O(xloglogx) 次基本标记操作,存储空间与 x 成正比。分段筛依次处理各个区间,从而降低内存需求,同时保留不超过 x 的素数,用来标记合数。
当还需要得到素数本身时,筛法尤其有用。如果只需要素数的个数,则可以采用更专门的算法,避免逐一枚举不超过 x 的所有素数。
勒让德公式
设 p1,p2,… 为按递增顺序排列的素数,并用 ϕ(x,a) 表示不超过 x、且不被前 a 个素数中的任何一个整除的正整数个数。这个辅助函数不是欧拉函数。
它满足递推关系
ϕ(x,a)=ϕ(x,a−1)−ϕ(pax,a−1),ϕ(x,0)=⌊x⌋.
若 a=π(x),则
π(x)=ϕ(x,a)+a−1.
这一恒等式源于如下事实:每个不超过 x 的合数都有一个不超过 x 的素因子。去掉这些素数的倍数后,剩下的只有 1 和大于 x 的素数。
迈塞尔–莱默方法以及后来的组合算法,通过按照素因子对剩余整数进行分类,进一步改进了这一思路。解析算法则利用ζ函数恒等式及误差可控的近似。这两类方法都能在不列出全部待计数素数的情况下,计算出精确的素数个数。
历史发展
素数表帮助人们发现,素数出现的频率大致遵循对数规律递减。18世纪末至19世纪初,卡尔·弗里德里希·高斯和阿德里安-马里·勒让德提出了影响深远的素数计数函数近似式。高斯将素数密度与 1/logx 联系起来,由此得到对数积分近似;勒让德则提出了形如 x/(logx−B) 的近似式。
19世纪中叶,帕夫努季·切比雪夫建立了一些界,表明 π(x) 与 x/logx 具有相同的数量级,但未能证明两者之比趋于 1。
1859年,波恩哈德·黎曼将素数计数与ζ函数的解析性质联系起来。1896年,雅克·阿达马和夏尔·让·德·拉瓦莱·普桑各自独立证明了素数定理,其证明的关键之一是表明ζ函数在直线 Re(s)=1 上没有零点。
1949年,阿特勒·塞尔伯格和保罗·埃尔德什给出了素数定理的初等证明。这里的“初等”是指证明不使用复分析方法,而不是说证明很简单。
相关计数问题与局限
若以 pn 表示第 n 个素数,则
π(pn)=n,pn=min{m∈N:π(m)≥n}.
因此,由素数定理可得
pn∼nlogn.
区间内的素数个数可表示为
π(x+h)−π(x),
即 (x,x+h] 中的素数个数。仅凭素数定理,并不能对任意选取的短区间长度 h,都将这个表达式替换为 h/logx。将两个全局近似式相减,剩余的误差可能比区间内的素数个数本身还大。
进一步的推广是统计剩余类中的素数:
π(x;q,a)=#{p≤x:p≡a(modq)}.
对于固定的正整数 q,当 a 与 q 互素时,算术级数中的素数定理指出
π(x;q,a)∼φ(q)li(x),
其中,φ 为欧拉函数。如果 q 随 x 增大,则相应结论需要附加条件和更强的估计。
因此,全局素数计数描述的是平均分布,但仅凭它们并不能确定单个素数间隔、素数模式或极短区间中的素数分布。