其实求\(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