$\pi(x)$ 的计算

$\pi (x)$ 表示不超过 $x$ 的素数个数。容易看出可以在 $O(N)$ 时间复杂度，$O(N)$ 空间复杂度离线预处理求出小于 $N$ 的素数全体。但是如果 $N={10}^{14}$ 或者更大，这种做法必然是不现实的。因此下面给出高效的求解方法...

理论基础: 参考潘承洞《数论基础》以及论文包.zip

$\psi (x,s)$

$\psi (x,s)$ 表示不超过 $x$ 且能不能被前 $s$ 个素数整除的正整数个数。即 $$\psi (x,s)=\sum _{n\le x}\sum _{d|(n,m_s)}\mu (d)=\sum _{d|m_s}u(d)\lfloor \frac{x}{d}\rfloor$$ 其中 $m_s=p_1\cdots p_s$ 为前 $s$ 个素数的积。

另一方面，显然我们有 $$\psi (x,s)=\psi (x,s-1)-\psi (\frac{x}{p_s},s-1)$$

$\pi (x)$

我们知道一个数 $n>1$ 是素数当且仅当不存在素数 $p\le \sqrt{n}$ 使得 $p\mid n$。因此当 $s\ge \pi (\sqrt{x})$ 时， $$\psi (x,s)=\pi (x)-s+1$$

$P_k(x,s)$

设 $P_k(x,s)$ 为 不超过 $x$ 且每个素因子都大于 $p_s$ 且素因子(按重根计)个数为 $k$ 的整数个数（方法属于 Lehmer）。 进一步设 $P_0(x,s)=1$。则 $$\psi (x,s)=\sum _{k=0}^{\mathrm{\infty }}{P}_k(x,s)$$ 显然 $P_1(x,s)=\pi (x)-s$。

若 $$$$ 则 $$$$ 此时 $$$$ 其中 $$$$

注意到上式中 $$$$

$$$$ 的计算公式

$$$$

取上面 $$$$ 因此问题最终转化成求 $$$$。它可以利用

1. $$$$
2. $$$$

至此问题貌似就这么解决了。但是由于这个递归会使得程序效率大大降低，因此需要一些预处理操作。

1. 若 $$$$ 则 $$$$
2. 给定一个小整数 M，预处理出 $$$$,其中 $$$$ 则 $$$$

lehmer 计算公式

我自己写的代码没有上面的快，两种计算各有优势

令 $$$$。则，对任意 $$$$, $$$$

即： $$$$

注意到 $$$$ ，所以最后一个式子可以用下式求，最后计算复杂度在于 $$$$

$$$$

稳定简洁的 DP 做法

我们令 $$$$ 它的意义是，$$$$ 中被前 $$$$ 个素数筛完后的伪素数个数。因此我们有 $$$$ 且有状态转移 $$$$ 因为 $$$$，最后一项可以写成 $$$$。虽然上面需要二维数组，但是实际上我们可以优化成一维数组的情况。因为 $$$$ 另外我们也不可能开 $$$$ 的数组，但是可以利用一种黑科技开 $$$$ 的数组即可达到我们的目的。 即我们用 $$$$ 表示 $$$$ 用 $$$$ 表示 $$$$。

若$$$$ ，则说明 $$$$ 不能被前 $$$$ 个素数整除是第 $$$$ 个素数。

我们需要的是 $$$$

上述做法的时间复杂度为 $$$$ 且常数特别小，代码十分简洁。

这个骚方法还目前还没有找到其它的应用 0.0

主要还没法对它用树状数组

求第 n 个素数的方法

• 根据概率分布找到大致界限
• 再牛顿梯度法（或者二分查找）使得 $$$$
• 素数判断递减 $$$$ 直到 $$$$ 为素数
• 参考这里

$$$$ 计算太慢了，需要优化

我们知道，若 $$$$ 则 $$$$ 其中 $$$$

注意到上式中 $$$$

我们之前的操作本质是递归让 $$$$ 变小，通过打表预处理来加速递归使得满足一定的效率需要。

现在我们来直接计算得到我们的答案。

符号约定

取定整数 $$$$ ，约定 $$$$ 是素数。 预处理 $$$$ 以内的数组：isp[], p[], mu[], pi[] ，对 $$$$ 内的 $$$$ 用树状数组（可以在我的博客网站搜索：树状数组）维护（注意到这需要 $$$$ 的内存，单次维护不现实，所以我们可以一段段的维护，保证每一段的长度为 $$$$ 来提高效率）

做完上面的预处理后，我们发现 $$$$ 可以直接计算了。

$$$$ 直接计算

在本博文的最开始有： $$$$ 其中 $$$$ 为前 $$$$ 个素数的积。

但是最右边本质上有很多项，所以直接算，其实复杂度特别高。

我们还有递归公式： $$$$ 可以一直分解下去，如果一直分解下去就可以得到最上面的公式了。

所以我们约定：对于节点 $$$$ ，如果满足

• 原始节点： $$$$
• 特殊节点：$$$$

就不再分解。这也等价于说 如果 $$$$ 且 $$$$ 就分解。因为一开始 $$$$。而且 $$$$ 会增大，$$$$ 会减小，所以节点一定会有限步内，落入上述两种框架中的一种。并且 特殊节点的父节点 $$$$ 必然满足 $$$$ 且 $$$$。综上：

以前设置 $$$$，但是后来发现没必要，$$$$ 就挺好。

$$$$

$$$$ 很好处理，计算 $$$$： 对 $$$$ 一起求： $$$$ 注意到：$$$$ ，所以我们已经可以把 $$$$ 直接计算出来了。

但是我们可以避免很多计算来提高效率。于是我们有下列一系列的操作

• $$$$，则 $$$$ 为素数 ，且此时 $$$$ (若 $$$$ 为合数，则 $$$$ 矛盾)
• $$$$ 时，$$$$
• $$$$ 时，$$$$
• $$$$

由此对$$$$分段计算

$$$$

$$$$

$$$$

$$$$

由限制关系式，我们化简 $$$$ $$$$

$$$$

$$$$

$$$$ 也可以用 $$$$ 的式子求，只是效率不高。

$$$$ 中 $$$$，即可以直接求。

当然了还可以继续细化，但是我嫌麻烦就不想再细化了！

也就是现在的核心就是树状数组分段维护数据，然后每一段的总值要用数组存起来就好了。然后用这个数据结果计算 $$$$，然后就大功告成了 0.0

用 $$$$ 计算 $$$$，还是用 $$$$ 计算 $$$$ ，这是一个问题。

用树状数组维护的时候会有一个很大的问题就是：求和式中 每此动 $$$$ 整个维护就要从 $$$$ 重新维护一次很麻烦。这个问题没解决所以我不想写代码。

想把 $$$$ 的所有可能的值单调递增排列但是又不现实。

第 n 个素数

做法依赖于 $$$$ 的计算

素数定理( 这里就不证了)

$$$$

从而我们知道： $$$$ 其中，$$$$ 为第 $$$$ 个素数，显然 $$$$ 是 $$$$ 最小的解。

$$$$ 求解

• 预处理小于 $$$$ 的素数
• 初始值 $$$$
• 牛顿梯度法

第 $$$$ 个素数和 $$$$ 的网站

世界纪录保持者的求法

$$$$

我们可以在不求出 不超过 $$$$ 的所有素数 的情况下，求出最终结果。

$$$$

• $$$$
• $$$$ 这是我们关心的结果
• 对于一般的 $$$$ 借助自然数方幂和快速算法也可以求

$$$$：最小素因子大于 $$$$ 且不超过 $$$$ 的数的 $$$$ 次方和

$$$$ 其中，$$$$ 表示 $$$$ 的最小素因子（约定 $$$$）。

$$$$ 的递推公式

$$$$

$$$$

$$$$ 和 $$$$ 的关系

若 $$$$，则 $$$$

其实我们还可以，类似于 $$$$ 的计算一样, 取 $$$$ $$$$