厄拉多塞筛法的递归实现(Python)

厄拉多塞筛法

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

代码实现

import math


def 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循环中,又重复筛除了一次。
  • 利用递归造成的存储开销也增大,每次递归需要额外存储一次lstlst_p

改进措施:

  • 尝试将递归改成循环(待续)。

热门相关:最强狂兵   寂静王冠   苏醒的秘密   大神你人设崩了   寂静王冠