Sieve of Eratosthenes set-实现混乱

Question

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

我正在查看下面 link 中找到的代码：

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

最后一行：

multiples.update(range(i*i, n+1, i))

将 i 的所有倍数从 i 的平方到 n 添加到集合 multiples 中。 i 的平方以下的任何倍数都已经在之前 i.

的集合中

Rosetta 没有说算法是 O(log(n))，它当然不是，只是集合查找是 O(log(n)) 与列表 O(n)。原因是集合使用散列作为查找的方式，实际上平均 O(1) 与 O(n)

Answer 2

表达式 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 是素数（因为它没有在筛子中找到），并且 [=11= 的下一个最小倍数] 不在 multiples 中是 i × i。证明：如果 i 的下一个最小倍数的值等于 c × i 对于某些 c 其中 1 < c < i，那么我们已经在筛子中将其过滤掉了.我们在 n+1 结束范围，因为那是筛子结束的地方（1 弥补了结束边界不包含的事实）。当然，我们的间隔设置为 i 以产生它的倍数。

关于 O(log(n)) 的一点是指在公共集实现中测试集成员资格的时间复杂度，而不是指完整的算法。整个算法的复杂度不能低于O(n)，因为外层循环运行了n-1次（从2到n）。实际上，集合成员资格测试需要 O(1) 时间，因为 Python 集合是哈希表。或者，您可以使用 n bool 的 list，这会以 space.

为代价获得更好的性能

Sieve of Eratosthenes set-实现混乱

Sieve of Eratosthenes set-implementation confusion

python

sieve-of-eratosthenes