厄拉多塞筛法

由古希腊厄拉多塞提出的算法（又称埃氏筛法），可以筛选出给定整数\(N\)以内的质数。
现给出一种利用递归实现厄拉多塞筛法的代码。

代码实现

import mathdef es(N):    if N <= 1:        return []    if N == 2:        return [2]    if N == 3:        return [2, 3]    lst = [1 for x in range(1, N+1)]    lst_p = es(math.floor(math.sqrt(N)))    for p in lst_p:        for i in range(p*2, N+1, p):            lst[i-1] = 0    return [i for i in range(2, N+1) if lst[i-1]]

复杂度分析

设递归的次数为\(k\)，则\(k\)满足：

\[\begin{align*}&N^{(\dfrac{1}{2})^k}\;=\;2\quad\quad\quad\quad\quad\quad\quad\quad \\&(\dfrac{1}{2})^k\log{N}=\log2 \\&k\log{\dfrac{1}{2}}=\log(\frac{\log2}{\log N}) \\&k= \dfrac{1}{\log2}\log{\dfrac{\log N}{\log2}}=\mathbb{O}(\log\log N)\end{align*}\]

由于lst_p是\(\sqrt{N}\)以内的素数表，因此第一个for循环的次数为\(\mathbb{O}(\sqrt{N})\).
第二个for循环的次数依\(p\)而定，为\(\lfloor\dfrac{N}{p}\rfloor-1\).
因此两次for循环的总次数\(m\)最多为：

\[\begin{align*}&m=\sum\limits_{p=1}^{\sqrt N}(\lfloor\dfrac{N}{p}\rfloor-1)\le N\sum\limits_{p=1}^{\sqrt N}\dfrac{1}{p}\;-\sqrt{N}<N\log\sqrt N\;-\sqrt N=\mathbb{O}(N\log N)\end{align*}\]

则总的时间复杂度为\(k\cdot m=\mathbb{O}(N\log N\log\log N)\).

小结

优点：

  • 相比于暴力解法(\(\mathbb{O}(N^2)\))，算法复杂度降到了\(\mathbb{O}(N\log N\log\log N)\)。
  • 相比于依赖质数表的解法，省去了质数表的存储。

不足：

  • 相比于最优解法(\(\mathbb{O}(N\log\log N)\))，算法复杂度多出一个乘积项\(\log N\)，原因是在每次递归得到lst_p时，\(\sqrt{N}\)以内的合数已被筛除一次。而在两次for循环中，又重复筛除了一次。
  • 利用递归造成的存储开销也增大，每次递归需要额外存储一次lst和lst_p。

改进措施：

  • 尝试将递归改成循环（待续）。