其实求 \(x\) 以内素数个数,有时间复杂度为 \(O(x^{2/3}loglogx)\),空间复杂度为 \(O(x^{1/3})\)优秀算法

\(prime(i)\) 表示第 \(i\) 个素数。

\(\pi(x)\) 表示小于等于 \(x\) 的素数个数。

\(\phi(x, a)\) 表示小于等于 \(x\) 的数中,不被前 \(a\) 个素数整除的数的个数,特别地,\(\phi(x, 0) = x\)

\(\phi(x, a)\) 分类,其中 \(P_k(x, a)\) 表示小于等于 \(x\) 的数中,不被前 \(a\) 个素数整除且有且仅有 \(k\) 个素数因子的数的个数,特别地,\(P_0(x, a) = 1\)。那么有,\(\phi(x,a) = P_0(x, a) + P_1(x, a) + \dots + P_k(x, a) + \dots\)

考虑到,

\[\pi(x) = P_1(x, a) + a = \phi(x, a) - P_0(x, a) - \sum_{k = 2}^{\infty}P_k(x, a) + a = \phi(x, a) -1 - \sum_{k = 2}^{\infty}P_k(x, a) + a\]

所以,对于特定的 \(a\),我们只需要知道 \(\phi(x, a)\)\(\sum_{k = 2}^{\infty}P_k(x, a)\),就可以计算出 \(\pi(x)\)

\(a = \pi(x ^ {1 / 3})\),那么 \(P_3(x, a) = P_4(x, a) = \dots = 0\),也就是说我们只需要计算 \(\phi(x, a)\)\(P_2(x, a)\)

先考虑如何计算 \(\phi(x, a)\)

注意到 \(\phi(x, a - 1)\)\(\phi(x, a)\) 多了那些不被前 \(a - 1\) 个素数整除但可以被 \(prime(a)\) 整除的数,即多了 \(\phi(\frac{x}{prime(a)}, a - 1)\)。因此,\(\phi(x, a) = \phi(x, a - 1) - \phi(\frac{x}{prime(a)}, a - 1)\)

我们解这个递归式就可以计算出 \(\phi(x, a)\)

假设我们能够解这个递归式,那么我们如何计算时间复杂度呢?

因为这个递归树是一棵满二叉树,所以叶子结点个数 \(n_0\) 与非叶结点个数 \(n_2\) 满足 \(n_0 = n_2 + 1\),也就是说时间复杂度为 \(O(n_0 + n_2) = O(2n_0 - 1) = O(n_0)\),因此我们只需要考虑递归树的叶子结点就好了。

因为递归树上的任一结点都可以被唯一地表示为 \(\phi(\frac{x}{n}, b)\),那么有一个显然的递归边界如下:

  1. \(b = 0\)\(\phi(\frac{x}{n}, b) = \frac{x}{n}\)
  2. \(\frac{x}{n} \leq prime(b)\)\(\phi(\frac{x}{n}, b) = 1\)

不过可以证明,这样的递归边界会使时间复杂度至少为 \(\Omega(\frac{x}{log^3x})\)。考虑 \(n\)\(3\) 个小于等于 \(x^{1/3}\) 的素数的乘积,由于 \(prime(b) \leq x^{1/3}\),因此必定存在叶子结点 \(\phi(\frac{x}{n}, b)\)。根据素数定理,小于等于 \(x^{1/3}\) 的素数大概有 \(\frac{x^{1/3}}{logx^{1/3}}\) 个,故递归树至少有 \(\Omega(\frac{x}{log^3x})\) 个叶子结点,达不到之前所说 \(O(x^{2/3}loglogx)\) 这样的时间复杂度。

现在考虑修改递归边界如下:

  1. \(b = 0\) 并且 \(n \leq x^{1/3}\)
  2. \(n > x^{1/3}\)

Read More