专栏文章

The Meissel, Lehmer, Lagarias, Miller, Odlyzko method (1996)

ケケロシブルアカ
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mimxe4pp
此快照首次捕获于
2025/12/01 17:07
3 个月前
此快照最后确认于
2025/12/01 17:07
3 个月前
查看原文
相信大家已经学会了 Computing π(x)\pi(x): The Meissel-Lehmer method(1985)，
今天我们来学一种更厉害的算法：Computing π(x)\pi(x): The Meissel, Lehmer, Lagarias, Miller, Odlyzko method (1996)
由于太过复杂，我会稍微弱化一下，跳过一些部分。

一些记号

π(x)\pi(x) 表示小于等于 xx 的素数个数。
pp 表示某个素数，pip_i 表示第 ii 个素数。

计算 π(x)\pi(x)

我们定义两个函数。
ϕ(x,a)\phi(x,a) 表示小于等于 xx 中所有质因子大于 pap_a 的数的个数，即：
ϕ(x,a)=∣{n≤x:p∣n⇒p>pa}∣\phi(x,a)= | \{ n \le x : p \mid n \Rightarrow p > p_a \} |
Pk(x,a)P_k(x,a) 表示小于等于 xx 的数中，有多少个是由 kk 个大于 pap_a 的质数相乘得来，即：
Pk(x,a)=∣{n≤x:n=∏j=1kpmj,mj>a}∣P_k(x,a)= \left | \left \{ n \le x : n = \prod_{j=1}^{k}p_{m_j},m_j > a \right \} \right |
不难发现等式：
ϕ(x,a)=P0(x,a)+P1(x,a)+P2(x,a)+⋯\phi(x,a)=P_0(x,a)+P_1(x,a)+P_2(x,a)+\cdots
不难发现若 pa≥x13p_a \ge x^\frac{1}{3}，则对于 k≥3k \ge 3 的 Pk(x,a)P_k(x,a) 都是 00。
所以取 y=⌊x13⌋y=\left \lfloor x^\frac{1}{3} \right \rfloor ，a=π(y)a=\pi(y)，那么有：
ϕ(x,a)=P0(x,a)+P1(x,a)+P2(x,a)\phi(x,a)=P_0(x,a)+P_1(x,a)+P_2(x,a) ϕ(x,a)=1+π(x)−a+P2(x,a)\phi(x,a)=1 + \pi(x)-a+P_2(x,a) π(x)=ϕ(x,a)−P2(x,a)+a−1\pi(x)=\phi(x,a) - P_2(x,a) + a - 1

计算 P2(x,a)P_2(x,a)

枚举小的质数，那么：
P2(x,a)=∑y<p≤x12π(np)−π(p)+1P_2(x,a)= \sum_{y < p \le x^\frac{1}{2}} \pi \left ( \frac{n}{p} \right ) - \pi(p) + 1

计算 ϕ(x,a)\phi(x,a)

考虑在 ϕ(x,a−1)\phi(x,a-1) 的基础上筛掉最小质因数为 pap_a 的数：
ϕ(x,a)=ϕ(x,a−1)−ϕ(xpa,a−1)\phi(x,a) = \phi(x, a - 1) - \phi \left (\frac{x}{p_a},a-1 \right )
终止条件：ϕ(x,0)=x\phi(x,0)=x。
可以看成是一个点疯狂分裂

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...