5

Eratosthenes 筛法是一种相当快的生成素数的方法，其限制k如下：

  1. 从集合p = (2, 3, 4, ..., k)和开始i = 2。
  2. 从 开始，删除fromi^2的所有倍数。ip
  3. 重复下一个最小i的p，直到i >= sqrt(k)。

我当前的实现看起来像这样（对预过滤所有偶数进行了明显的优化）：

# Compute all prime numbers less than k using the Sieve of Eratosthenes
def sieve(k):
    s = set(range(3, k, 2))
    s.add(2)

    for i in range(3, int(sqrt(k)), 2):
        if i in s:
            for j in range(i ** 2, k, i * 2):
                s.discard(j)

    return sorted(s)

编辑：这是基于等效list的代码：

def sieve_list(k):
    s = [True] * k
    s[0] = s[1] = False
    for i in range(4, k, 2):
        s[i] = False

    for i in range(3, int(sqrt(k)) + 2, 2):
        if s[i]:            
            for j in range(i ** 2, k, i * 2):
                s[j] = False

    return [2] + [ i for i in range(3, k, 2) if s[i] ]

这有效，但并不完全正确。这些行：

for i in range(3, int(sqrt(k)), 2):
    if i in s:
        [...]

s通过测试每个奇数的集合成员关系找到下一个最小元素。理想情况下，实现实际上应该是：

while i < sqrt(k):
    [...]
    i = next smallest element in s

但是，由于set是无序的，我不知道如何（或者即使可能）以更有效的方式获得下一个最小元素。我考虑过使用list带有True/False标志的素数，但您仍然必须步行list寻找下一个True元素。您不能只从其中list任何一个中实际删除元素，因为这使得在步骤 2 中有效地删除复合数字成为不可能。

有没有办法更有效地找到下一个最小的元素？如果没有，是否有其他数据结构允许O(1)按值删除以及找到下一个最小元素的有效方法？

4

2 回答 2

7

集合是无序的，因为它们在内部实现为哈希集。在这样的数据结构中没有找到最小元素的有效方法；min(s)将是最 Pythonic 的方式（但它是 O(n)）。

您可以将 acollections.deque 与您的套装一起使用。使用deque来按排序顺序存储元素列表。每次你需要得到最小值时，弹出元素，deque直到你找到你的集合中的一个。这已经在整个输入数组中摊销了 O(1) 成本（因为您只需弹出 n 次）。

我还应该指出，不可能有从列表（或 O(1) 插入）创建 O(n)、按值删除 O(1) 和 O(1) 最小查找的数据结构；这样的数据结构可以用来简单地实现 O(n) 的一般排序，这是（信息论的）不可能的。哈希集非常接近，但必须牺牲有效的最小查找。

于 2012-09-16T16:19:21.420 回答
0

您可以使用列表代替集合。使用 None 初始化列表以表示未标记。您可以使用元素索引作为数字。

  1. 初始化列表
  2. 从 p = 2 开始
  3. p用'M'标记列表中的所有倍数以表示标记
  4. 在列表中找到下一个未标记的元素并将其设为新的p. 如果没有，你就完成了。

如果您需要找到下一个未标记的索引，您可以简单地查看索引之后的元素p并且等于无。

于 2012-09-16T16:01:49.213 回答