Python- 埃拉托斯特尼筛法- 精简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和filter，但总是搞不对。

我在考虑像这样的写法：

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部分：

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

你没有在使用埃拉托斯特尼筛法；如果算法没有正确实现，可能会非常慢。比如，你可以试着用 10**6 来测试你的算法。

我能想到的最简短的有界埃拉托斯特尼筛法实现是：

def primes(upTo):
    isPrime = list(range(upTo))
    for p in range(2,int(upTo**0.5)+1): #p: 2,3,4,...,sqrt(N)
        print(p, isPrime[p])
        if isPrime[p]:
            for multiple in range(p**2,upTo,p): #mult: p^2, p^2+p, p^2+2p, ..., N
                isPrime[multiple] = False
    return [x for x in isPrime[2:] if x]

演示：

>>> list(primes(29))
[2, 3, 5, 7, 11, 13, 17, 19, 23]

其实这个实现相当简洁，如果你忽略换行和跳过偶数的优化的话：

isPrime=[True]*upTo for p in range(2,upTo): if isPrime[p]: yield p for m in range(p,upTo,p): isPrime[m]=False

Answer 2

首先要注意的是，你写的并不是埃拉托斯特尼筛法。看看一个完全简单的埃拉托斯特尼筛法要执行多少次循环：

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)

对于100个数字，它执行了102次循环（不包括最后的过滤）。现在看看你的实现：

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

Answer 3

这段话并不是直接把你的循环翻译过来，但它很接近，而且写得比较简洁：

>>> l = range(2, 101)
>>> sorted(set(l).difference(a for i in l for a in l if a!=i and a%i == 0))
[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]

不过我建议用 a > i，比起 a != 0，这样写更短也更快哦；)