python - Sieve of Eratosthenes set-实现困惑

Question

我想首先说明我是一个 python 新手，我很感激任何能向我清楚、完整地解释它的人。

我正在查看以下链接中的代码:

http://rosettacode.org/wiki/Sieve_of_Eratosthenes#Python

我刚刚开始了解迭代器、生成器和 yield 命令，但我不了解代码如何实现集合。

def eratosthenes2(n):
    multiples = set()
    for i in range(2, n+1):
        if i not in multiples:
            yield i
            multiples.update(range(i*i, n+1, i))

我很难理解此函数的最后一行的作用。

此外，有人可以向我解释为什么这个实现是 O(log(n)) 时间吗？

Answer 1

表达式range(i, j, k)生成来自 i 的整数列表至 j (j 是非包容性的，因此包容性边界是 j-1 )，间隔为 k (默认情况下为 1)。所以range(2, 10, 2)生成列表 [2, 4, 6, 8] .

最后一行所做的是插入 i 的所有倍数来自 i ² 到 n到集multiples .我们从 i 开始² 因为 i是一个质数(因为它没有在筛子中找到)，并且是 i 的下一个最小倍数不在 multiples是i × i .证明:如果 i 的下一个最小倍数值等于 c × i对于某些 c，其中 1 < c < i ，那么我们已经在筛子中将其过滤掉了。我们在 n+1 处结束范围因为那是筛子结束的地方(1 弥补了结束边界不包含的事实)。当然，我们的间隔设置为 i产生它的倍数。

关于 O(log(n)) 的一点是指在公共(public)集实现中测试集成员资格的时间复杂度，而不是指完整的算法。整个算法的复杂度不能低于O(n)，因为外层循环运行n -1 次(从 2 到 n)。实际上，集合成员资格测试需要 O(1) 时间，因为 Python 集合是哈希表。或者你可以使用 list的 n bool s，这将以空间为代价获得更好的性能。