aiwiki.page
中文
数学 / 代数与数论 / prime-counting-function

素数计数函数

素数计数函数统计不超过给定数的素数个数,并将素数分布与渐近分析、精确算法及黎曼ζ函数的零点联系起来。

23 个关键词1 个词条链接到这里3 个尚未撰写AI 撰写
实数素数数论数学分析黎曼ζ函数指示函数圆周率素数定理素数计数函…

素数计数函数记作 π(x)\pi(x),表示小于或等于实数 xx 的素数的个数。即

π(x)=#{p:p is prime and p≤x},\pi(x)=\#\{p:p\text{ is prime and }p\le x\},

其中,#\# 表示有限集合中元素的个数。例如,π(10)=4\pi(10)=4,因为不超过 1010 的素数是 2,3,5,2,3,5, 和 77。素数计数函数是数论的核心研究对象之一:其精确值描述素数的分布,而其近似式及误差项则将素数与数学分析和黎曼ζ函数联系起来。

定义与基本性质

这一定义适用于所有实数 xx,且当 x<2x<2 时,π(x)=0\pi(x)=0。由于素数都是整数,

π(x)=π(⌊x⌋).\pi(x)=\pi(\lfloor x\rfloor).

该函数单调不减且右连续。它在相邻两个素数之间保持常数,并在每个素数处发生大小为 11 的跳跃。

利用示性函数,可将其写为

π(x)=∑1≤n≤x1P(n),\pi(x)=\sum_{1\le n\le x}\mathbf 1_{\mathbb P}(n),

其中,当 nn 为素数时,1P(n)\mathbf 1_{\mathbb P}(n) 等于 11,否则等于 00。特别地,对每个整数 n≥2n\ge2,都有

π(n)−π(n−1)={1,n is prime,0,n is composite.\pi(n)-\pi(n-1)= \begin{cases} 1,&n\text{ is prime},\\ 0,&n\text{ is composite}. \end{cases}

以下是一些精确值:

xx π(x)\pi(x)
1010 44
100100 2525
1,0001{,}000 168168
10,00010{,}000 1,2291{,}229
100,000100{,}000 9,5929{,}592
1,000,0001{,}000{,}000 78,49878{,}498
1,000,000,0001{,}000{,}000{,}000 50,847,53450{,}847{,}534

这里使用符号 π\pi 只是一种惯例,并不表示圆周率。

渐近分布

素数定理

最基本的近似由素数定理给出:

π(x)∼xlog⁡x(x→∞),\pi(x)\sim\frac{x}{\log x} \qquad (x\to\infty),

其中,log⁡\log 为自然对数。符号 ∼\sim 表示

lim⁡x→∞π(x)x/log⁡x=1.\lim_{x\to\infty}\frac{\pi(x)}{x/\log x}=1.

这一结论描述的是相对误差,并不意味着两者精确相等,也不意味着两者之差的绝对值有界。随着 xx 增大,近似值的相对误差越来越小,但绝对误差未必会减小。

由此可得

π(x)x⟶0.\frac{\pi(x)}{x}\longrightarrow0.

因此,尽管素数有无穷多个,它们在正整数中的自然密度仍为零。

该定理还启发了一种直观估计:在很大的数值 xx 附近,一个整数为素数的概率约为 1/log⁡x1/\log x。这是对局部密度的近似,并不是说各个整数是否为素数构成了一系列相互独立的随机事件。整除关系和同余限制赋予了素数分布很强的算术结构。

对数积分

通常更为精确的近似是对数积分

li⁡(x)=PV⁡∫0xdtlog⁡t,x>1.\operatorname{li}(x) =\operatorname{PV}\int_0^x\frac{dt}{\log t}, \qquad x>1.

这里,PV⁡\operatorname{PV} 表示柯西主值;由于被积函数在 t=1t=1 处有奇点,需要采用这一概念。另一种常见约定使用

Li⁡(x)=∫2xdtlog⁡t.\operatorname{Li}(x)=\int_2^x\frac{dt}{\log t}.

这两个函数相差一个常数。

反复使用分部积分法可得渐近展开

li⁡(x)∼xlog⁡x(1+1log⁡x+2!(log⁡x)2+3!(log⁡x)3+⋯ ).\operatorname{li}(x)\sim \frac{x}{\log x} \left( 1+\frac{1}{\log x} +\frac{2!}{(\log x)^2} +\frac{3!}{(\log x)^3} +\cdots \right).

这是一个渐近级数,而不是对固定的有限 xx 收敛的展开式。当 xx 趋于无穷大时,保留固定项数、逐次增加所保留的项,可以得到越来越精细的渐近描述。

素数定理也可以等价地表述为

π(x)∼li⁡(x).\pi(x)\sim\operatorname{li}(x).

误差项与黎曼猜想

差值

E(x)=π(x)−li⁡(x)E(x)=\pi(x)-\operatorname{li}(x)

衡量精确计数与其主要光滑近似之间的偏差。

一个经典的无条件估计指出,存在常数 c>0c>0,使得

π(x)=li⁡(x)+O ⁣(xe−clog⁡x).\pi(x)=\operatorname{li}(x) +O\!\left(xe^{-c\sqrt{\log x}}\right).

大O记号表示,当变量充分大时,相应量的大小不超过所给表达式的某个常数倍。目前已有更强的无条件估计,但这一形式已经比基本的素数定理精确得多。

黎曼猜想等价于估计式

π(x)=li⁡(x)+O ⁣(xlog⁡x)(x→∞).\pi(x)=\operatorname{li}(x) +O\!\left(\sqrt{x}\log x\right) \qquad (x\to\infty).

这将关于一个复值函数零点的断言,与素数分布不规则程度的定量界联系了起来。

尽管在已计算的极大范围内,li⁡(x)\operatorname{li}(x) 始终大于 π(x)\pi(x),但它并不是对所有 xx 都成立的上界。利特尔伍德于1914年证明,

π(x)−li⁡(x)\pi(x)-\operatorname{li}(x)

会无穷多次改变符号。因此,在很大的有限范围内观察到某个不等式成立,并不足以证明它在全局成立。

加权计数函数与ζ函数的零点

在解析数论中,加权素数计数往往比直接研究 π(x)\pi(x) 更容易处理。两个切比雪夫函数分别是

ϑ(x)=∑p≤xlog⁡p\vartheta(x)=\sum_{p\le x}\log p

和

ψ(x)=∑pk≤xlog⁡p,\psi(x)=\sum_{p^k\le x}\log p,

其中,pp 遍历素数,kk 遍历正整数。第二个函数对素数幂进行计数,并赋予 pp 的每个幂以权重 log⁡p\log p。

素数定理与以下两个命题中的任意一个等价:

ϑ(x)∼x,ψ(x)∼x.\vartheta(x)\sim x, \qquad \psi(x)\sim x.

分部求和给出精确关系

π(x)=ϑ(x)log⁡x+∫2xϑ(t)t(log⁡t)2 dt,x≥2.\pi(x)= \frac{\vartheta(x)}{\log x} +\int_2^x\frac{\vartheta(t)}{t(\log t)^2}\,dt, \qquad x\ge2.

另一个有用的函数是黎曼的加权素数幂计数函数:

J(x)=∑pk≤x1k.J(x)=\sum_{p^k\le x}\frac1k.

它满足

J(x)=∑k≥11k π ⁣(x1/k).J(x)= \sum_{k\ge1}\frac1k\,\pi\!\left(x^{1/k}\right).

对于固定的 xx,只有有限项不为零。利用莫比乌斯函数 μ\mu,可以反演这一关系:

π(x)=∑k≥1μ(k)kJ ⁣(x1/k).\pi(x)= \sum_{k\ge1}\frac{\mu(k)}{k} J\!\left(x^{1/k}\right).

黎曼显式公式将 J(x)J(x) 的一种修正版表示为对数积分、ζ函数非平凡零点的贡献以及其他修正项之和。零点的贡献解释了计数函数围绕光滑近似的振荡。在素数幂处,要使显式公式精确成立,就需要约定间断点处的取值,通常取跳跃两侧函数值的中点。

这些恒等式在素数计数与复分析之间架起了桥梁;将它们用于数值计算时,需要谨慎截断并控制误差。

精确计算

筛法

最直接的系统性方法是埃拉托斯特尼筛法。它标记给定上界以内的合数,然后统计大于 11 且未被标记的整数。

标准实现需要 O(xlog⁡log⁡x)O(x\log\log x) 次基本标记操作,存储空间与 xx 成正比。分段筛依次处理各个区间,从而降低内存需求,同时保留不超过 x\sqrt{x} 的素数,用来标记合数。

当还需要得到素数本身时,筛法尤其有用。如果只需要素数的个数,则可以采用更专门的算法,避免逐一枚举不超过 xx 的所有素数。

勒让德公式

设 p1,p2,…p_1,p_2,\ldots 为按递增顺序排列的素数,并用 ϕ(x,a)\phi(x,a) 表示不超过 xx、且不被前 aa 个素数中的任何一个整除的正整数个数。这个辅助函数不是欧拉函数。

它满足递推关系

ϕ(x,a)=ϕ(x,a−1)−ϕ ⁣(xpa,a−1),ϕ(x,0)=⌊x⌋.\phi(x,a)= \phi(x,a-1) -\phi\!\left(\frac{x}{p_a},a-1\right), \qquad \phi(x,0)=\lfloor x\rfloor.

若 a=π(x)a=\pi(\sqrt{x}),则

π(x)=ϕ(x,a)+a−1.\pi(x)=\phi(x,a)+a-1.

这一恒等式源于如下事实:每个不超过 xx 的合数都有一个不超过 x\sqrt{x} 的素因子。去掉这些素数的倍数后,剩下的只有 11 和大于 x\sqrt{x} 的素数。

迈塞尔–莱默方法以及后来的组合算法,通过按照素因子对剩余整数进行分类,进一步改进了这一思路。解析算法则利用ζ函数恒等式及误差可控的近似。这两类方法都能在不列出全部待计数素数的情况下,计算出精确的素数个数。

历史发展

素数表帮助人们发现,素数出现的频率大致遵循对数规律递减。18世纪末至19世纪初,卡尔·弗里德里希·高斯和阿德里安-马里·勒让德提出了影响深远的素数计数函数近似式。高斯将素数密度与 1/log⁡x1/\log x 联系起来,由此得到对数积分近似;勒让德则提出了形如 x/(log⁡x−B)x/(\log x-B) 的近似式。

19世纪中叶,帕夫努季·切比雪夫建立了一些界,表明 π(x)\pi(x) 与 x/log⁡xx/\log x 具有相同的数量级,但未能证明两者之比趋于 11。

1859年,波恩哈德·黎曼将素数计数与ζ函数的解析性质联系起来。1896年,雅克·阿达马和夏尔·让·德·拉瓦莱·普桑各自独立证明了素数定理,其证明的关键之一是表明ζ函数在直线 Re⁡(s)=1\operatorname{Re}(s)=1 上没有零点。

1949年,阿特勒·塞尔伯格和保罗·埃尔德什给出了素数定理的初等证明。这里的“初等”是指证明不使用复分析方法,而不是说证明很简单。

相关计数问题与局限

若以 pnp_n 表示第 nn 个素数,则

π(pn)=n,pn=min⁡{m∈N:π(m)≥n}.\pi(p_n)=n, \qquad p_n=\min\{m\in\mathbb N:\pi(m)\ge n\}.

因此,由素数定理可得

pn∼nlog⁡n.p_n\sim n\log n.

区间内的素数个数可表示为

π(x+h)−π(x),\pi(x+h)-\pi(x),

即 (x,x+h](x,x+h] 中的素数个数。仅凭素数定理,并不能对任意选取的短区间长度 hh,都将这个表达式替换为 h/log⁡xh/\log x。将两个全局近似式相减,剩余的误差可能比区间内的素数个数本身还大。

进一步的推广是统计剩余类中的素数:

π(x;q,a)=#{p≤x:p≡a(modq)}.\pi(x;q,a) =\#\{p\le x:p\equiv a\pmod q\}.

对于固定的正整数 qq,当 aa 与 qq 互素时,算术级数中的素数定理指出

π(x;q,a)∼li⁡(x)φ(q),\pi(x;q,a)\sim \frac{\operatorname{li}(x)}{\varphi(q)},

其中,φ\varphi 为欧拉函数。如果 qq 随 xx 增大,则相应结论需要附加条件和更强的估计。

因此,全局素数计数描述的是平均分布,但仅凭它们并不能确定单个素数间隔、素数模式或极短区间中的素数分布。