1

我正在尝试学习 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。

4

3 回答 3

2

筛子需要对候选素数的循环进行排序。有问题的代码是枚举字典的键，不能保证是有序的。相反，继续使用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]]
于 2013-04-20T00:10:20.160 回答
1

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

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

于 2013-04-20T00:04:16.073 回答
0

好吧，看看运行时间——你会看到你展示的最后一个案例的运行时间几乎比基准测试快 5 倍，而它通常慢 5 倍。所以这是一个危险信号，也许你没有执行所有的迭代？（而且它的速度快 5 倍，而素数几乎是 10 倍……）

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

于 2013-04-19T23:01:01.570 回答