python - 在 Python 中查找素筛不一致

Question

我正在尝试学习Python，我认为尝试开发自己的素筛将是下午的一个有趣的问题。到目前为止，当需要时，我只会导入我在网上找到的埃拉托斯特尼筛法的一个版本——我用它作为基准。

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

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]]