Python- Eratosthenes 筛法- 紧凑型 Python

Question

这是我使用埃拉托色尼筛法寻找素数的代码。

list = [i for i in range(2, int(raw_input("Compute primes up to what number? "))+1)]  

for i in list:
    for a in list:
            if a!=i and a%i == 0:
                list.remove(a)

试图找到一种方法将那些嵌套的 for 循环压缩成某种生成器或推导式，但似乎您无法使用推导式将函数应用于列表。我尝试使用 map 和过滤器，但我似乎无法正确使用。

思考这样的事情:

print map(list.remove(a), filter(lambda a, i: (a%i ==0 and a!=i), [(a, i) for i in list for a in list])

显然有很多原因行不通。如果我只是使用该代码的过滤器部分:

filter(lambda a, i: (a%i ==0 and a!=i), **[(a, i) for i in list for a in list]**

将两个变量放入 lambda 的正确方法是什么？ (a,i) 使它成为一个元组，但我想将“a”和“i”作为独立变量提交到 lambda 中。

我最终用这个单行解决了问题:

print sorted(set([i for i in range(2, int(raw_input("Compute primes up to what number? "))+1)]).difference(a for i in l for a in l if a!=i and a%i == 0))

Answer 1

首先要注意的是，你写的不是埃拉托色尼筛法。看看一个完全天真的埃拉托色尼筛执行了多少个循环:

def sieve1(n):
    loops = 0
    numbers = set(range(2, n))
    for i in range(2, int(n ** 0.5) + 1):
        for j in range(i * 2, n, i):
            numbers.discard(j)
            loops += 1
    return sorted(numbers), loops

测试:

>>> sieve1(100)
([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 
  43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97], 
 178)

100 个数字的 178 次循环(不包括排序)。这可以通过一些小的更改来改进:

def sieve2(n):
    loops = 0
    numbers = range(0, n)
    for prime in numbers:
        if prime < 2:
            continue
        elif prime > n ** 0.5:
            break
        for i in range(prime ** 2, n, prime):
            numbers[i] = 0
            loops += 1
    return [x for x in numbers if x > 1], loops

测试:

>>> sieve2(100)
([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 
  43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97], 
 102)

102 个循环用于 100 个数字(不包括末尾的过滤器)。现在看看你的:

def sieve3(n):
    loops = 0
    numbers = range(2, n)
    for i in numbers:
        for j in numbers:
            if j != i and j % i == 0:
                numbers.remove(j)
            loops += 1
    return numbers, loops

测试:

>>> sieve3(100)
([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 
  43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97], 
 663)

情况变得更糟:

>>> [sieve1(x)[1] for x in [100, 1000, 10000]]
[178, 2978, 41723]
>>> [sieve2(x)[1] for x in [100, 1000, 10000]]
[102, 1409, 16979]
>>> [sieve3(x)[1] for x in [100, 1000, 10000]]
[663, 28986, 1523699]

在 n = 10000 时，您的实现几乎完成了 100 倍的工作!

我的建议是先创建一个合理的实现，然后再使其“紧凑”。代码高尔夫可能很有趣，但它远不及编写高效代码那样具有挑战性或启发性，无论长度如何。

就是说，考虑这个单行代码(如果你不计算导入，你可以通过使用 lambda x, y: x - y 代替 来摆脱它operator.sub).这实现了第一个算法，稍作改进:

>>> from operator import sub
>>> reduce(sub, (set(range(x ** 2, 100, x)) for x in range(2, int(100 ** 0.5) + 1)), set(range(2, 100)))
set([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97])