在Python中查找素数筛不一致性

Question

我正在尝试学习python，我想尝试开发我自己的主筛子对于下午来说是一个有趣的问题。到目前为止，当需要时，我只需要导入我在网上找到的Eratosthenes筛子的一个版本--这就是我用作基准的筛子。

在尝试了几种不同的优化之后，我认为我已经写了一个相当不错的筛子：

def sieve3(n):
top = n+1
sieved = dict.fromkeys(xrange(3,top,2), True)
for si in sieved:
    if si * si > top:
        break
    if sieved[si]:
        for j in xrange((si*2) + si, top, si*2):       [****]
            sieved[j] = False
return [2] + [pr for pr in sieved if sieved[pr]]

使用前1,000,000个整数作为我的范围，此代码将生成正确的质数数量，并且仅比我的基准测试慢3-5倍。当我在更大的射程上尝试时，我正要放弃并拍拍自己的背，但它不再起作用了！

n = 1,000 -- Benchmark = 168 in 0.00010 seconds
n = 1,000 -- Sieve3 = 168 in 0.00022 seconds

n = 4,194,304 -- Benchmark = 295,947 in 0.288 seconds
n = 4,194,304 -- Sieve3 = 295,947 in 1.443 seconds

n = 4,194,305 -- Benchmark = 295,947 in 3.154 seconds
n = 4,194,305 -- Sieve3 = 2,097,153 in 0.8465 seconds

我认为问题出在[****]的问题上，但我不明白为什么它会这么坏。它应该将'j‘的每个奇数倍标记为False，并且它在大多数情况下都有效，但对于高于4,194,304的任何值，筛子都会损坏。(公平地说，它也会在随机的其他数字上中断，比如10,000 )。

我做了一个改变，这大大降低了我的代码速度，但它实际上对所有值都有效。这个版本包括所有数字(不仅仅是赔率)，但在其他方面是相同的。

def sieve2(n):
top = n+1
sieved = dict.fromkeys(xrange(2,top), True)
for si in sieved:
    if si * si > top:
        break
    if sieved[si]:
        for j in xrange((si*2), top, si):
            sieved[j] = False
return [pr for pr in sieved if sieved[pr]]

有人能帮我弄清楚为什么我的原始函数(sieve3)不能一致地工作吗？

编辑:我忘了提一下，当Sieve3‘中断’时，sieve3(n)返回n/2。

Answer 1

筛子需要对候选素数上的循环进行排序。所讨论的代码是枚举字典的键，而这些键并不保证是有序的。相反，继续使用您用来为主筛子循环和返回结果循环初始化字典的xrange，如下所示：

def sieve3(n):
    top = n+1
    sieved = dict.fromkeys(xrange(3,top,2), True)
    for si in xrange(3,top,2):
        if si * si > top:
            break
        if sieved[si]:
            for j in xrange(3*si, top, si*2):     
                sieved[j] = False
    return [2] + [pr for pr in xrange(3,top,2) if sieved[pr]]

Answer 2

这是因为字典键是没有排序的。有时候，for si in sieved:会按递增的顺序遍历您的键。在最后一个示例中，si获得的第一个值足够大，可以立即中断循环。

您可以简单地使用: for si in sorted(sieved)：

Answer 3

好的，看看运行时--您看到您展示的上一个案例的运行时几乎比基准测试快了5倍，而它通常要慢5倍。所以这是一个危险的信号，也许你没有执行所有的迭代？(它的速度是5倍，而素数几乎是它的10倍……)

我现在没有时间研究更多的代码，但我希望这对我有帮助。