

Meissel-Lehmer 算法

「Meissel-Lehmer 算法」是一种能在亚线性时间复杂度内求出内质数个数的一种算法。

记号规定¶

表示对下取整得到的结果。
表示第个质数，。
表示范围内素数的个数。
表示莫比乌斯函数。
对于集合，表示集合的大小。
表示最小的质因子。
表示最大的质因子。

Meissel-Lehmer 算法求 π(x)¶

定义为所有小于的正整数中满足其所有质因子都大于的数的个数，即：

再定义表示为所有小于的正整数中满足可重质因子恰好有个且所有质因子都大于的数的个数，即：

特殊的，我们定义：，如此便有：

这个无限和式实际上是可以表示为有限和式的，因为在时，有。

设为满足的整数，再记。

在时，有与，由此我们可以推出：

这样，计算便可以转化为计算与。

计算 P₂(x,a)¶

由等式我们可以得出等于满足且的质数对的个数。

首先我们注意到。此外，对于每个，我们都有。因此：

当时，我们有。因此，我们可以筛区间，然后对于所有的的质数计算。为了减少上述算法的空间复杂度，我们可以考虑分块，块长为。若块长，则我们可以在的时间复杂度，的空间复杂度内计算。

计算 ϕ(x,a)¶

对于，考虑所有不超过的正整数，满足它的所有质因子都大于。这些数可以被分为两类：

可以被整除的；
不可以被整除的。

属于第类的数有个，属于第二类的数有个。

因此我们得出结论：

定理： 函数满足下列性质

计算的简单方法可以从这个定理推导出来：我们重复使用等式，知道最后得到。这个过程可以看作从根节点开始创建有根二叉树，图画出了这一过程。通过这种方法，我们得到如下公式：

上图表示计算过程的二叉树：叶子节点权值之和就是。

但是，这样需要计算太多东西。因为，仅仅计算为个不超过质数的乘积的数，如果按照这个方法计算，会有至少个项，没有办法我们对复杂度的需求。

为了限制这个二叉树的“生长”，我们要改变原来的终止条件。这是原来的终止条件。

终止条件： 如果，则不要再对节点调用等式。

我们把它改成更强的终止条件：

终止条件： 如果满足下面个条件中的一个，不要再对节点调用等式 :

且；

。

我们根据 终止条件 将原二叉树上的叶子分成两种：

如果叶子节点满足，则称这种叶子节点为 普通叶子；
如果叶子节点满足且，则称这种节点为 特殊叶子。

由此我们得出：

定理： 我们有：

其中表示 普通叶子 的贡献：

表示 特殊叶子 的贡献：

计算显然是可以在的时间复杂度内解决的，现在我们要考虑如何计算。

计算 S¶

我们有：

我们将这个等式改写为：

其中：

注意到计算的和式中涉及到的都是质数，证明如下：

如果不是这样，因为有，所以有，这与矛盾，所以原命题成立。

更多的，当时，有。因此我们有：

计算 S₁¶

因为：

所以：

所以计算的和式中的项都是。所以我们实际上要计算质数对的个数，满足：。

因此：

有了这个等式我们便可以在的时间内计算。

计算 S₂¶

我们有：

我们将分成与两部分：

其中：

计算 U¶

由可得，因此：

因此：

因为有，所以我们可以预处理出所有的，这样我们就可以在的时间复杂度内计算出。

计算 V¶

对于计算的和式中的每一项，我们都有。因此：

所以可以被表示为：

其中：

预处理出我们就可以在的时间复杂度内计算出。

考虑我们如何加速计算的过程。我们可以把的贡献拆分成若干个为定值的区间上，这样我就只需要计算出每一个区间的长度和从一个区间到下一个区间的的改变量。

更准确的说，我们首先将分成两个部分，将这个复杂的条件简化：

接着我们把这个式子改写为：

其中：

计算 W₁ 与 W₂¶

计算这两个值需要计算满足的的值。可以在区间分块筛出。在每个块中我们对于所有满足条件的都累加。

计算 W₃¶

对于每个，我们把分成若干个区间，每个区间都满足它们的是定值，每个区间我们都可以计算它的贡献。当我们获得一个新的时，我们用（）的值表计算。以内的质数表可以给出使得成立的。以此类推使得变化的下一个的值。

计算 W₄¶

相比于，中更小，所以改变得更快。这时候再按照计算的方法计算就显得没有任何优势。于是我们直接暴力枚举数对来计算。

计算 W₅¶

我们像计算那样来计算。

计算 S₃¶

我们使用所有小于的素数一次筛出区间。当我们的筛法进行到的时候，我们算出了所有满足没有平方因子并且的值。这个筛法是分块进行的，我们在筛选间隔中维护一个二叉树，以实时维护所有素数筛选到给定素数后的中间结果。这样我们就可以只用的时间复杂度求出在筛法进行到某一个值的时候没有被筛到的数的数量。

算法的时空复杂度¶

时空复杂度被如下个过程影响：

计算；
计算；
计算。

计算 P₂(x,y) 的复杂度¶

我们已经知道了这个过程的时间复杂度为，空间复杂度为。

计算 W₁,W₂,W₃,W₄,W₅ 的复杂度¶

计算所进行的块长度为的筛的时间按复杂度为，空间复杂度为。

计算所需的时间复杂度为：

计算的时间复杂度为：

因此，计算的时间复杂度为：

计算的时间复杂度为：

计算 S₃ 的复杂度¶

对于预处理：由于要快速查询的值，我们没办法用普通的筛法求出，而是要维护一个数据结构使得每次查询的时间复杂度是，因此时间复杂度为。

对于求和：对于计算和式中的每一项，我们查询上述数据结构，一共次查询。我们还需要计算和式的项数，即二叉树中叶子的个数。所有叶子的形式均为，其中。因此，叶子的数目是级别的。所以计算的总时间复杂度为：

总复杂度¶

这个算法的空间复杂度为，时间复杂度为：

我们取，就有最优时间复杂度为，空间复杂度为。

一些改进¶

我们在这里给出改进方法，以减少算法的常数，提高它的实际效率。

在 终止条件 中，我们可以用一个来代替，其中满足。我们可以证明这样子计算的时间复杂度可以优化到：这也为通过改变的值来检查计算提供了一个很好的方法。
为了清楚起见，我们在阐述算法的时候选择在处拆分来计算总和，但实际上我们只需要有就可以计算。我们可以利用这一点，渐近复杂性保持不变。
用前几个素数预处理计算可以节省更多的时间。

参考资料与拓展阅读¶

本文翻译自：Computing : the Meissel, Lehmer, Lagarias, Miller, Odlyzko method

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Peanut-Tang, Early0v0, Vxlimo, GHLinZhengyu, 1196131597
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用