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

- Parseltongue

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)

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

- senderle

---

这非常令人印象深刻且极具教育意义。我是一个编程新手，所以对于它的低效率表示歉意 :-\ - Parseltongue

@Parseltongue，不需要为此道歉——每个人都会写出低效的代码！如果我有所冒犯，那么请接受我的道歉——我的关注点并不是效率，而是作为程序员应该优先考虑什么。公平地说，有时候追求紧凑性很重要；只是过度压缩的代码很少是理想的。 - senderle

Answer 2

这并不是对您的循环的直接翻译，但它非常接近且紧凑：

>>> 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，因为它更短更快 ;)

- spiv

---

"TypeError: 'type' object is not iterable" - 有什么想法吗？ - Parseltongue

@Parseltongue，我敢打赌这是因为你使用了list，也就是内置的列表构造函数作为变量名。 - senderle

我同意。我的目标只是简洁地表达原始代码，正如所要求的那样。这个网站上还有很多其他关于寻找质数更有效方法的问题！ - spiv

这个实现的运行时间非常糟糕（因此不能合理地称之为埃拉托斯特尼筛法）。当然，对于小数字来说，这是一种简洁的方法，这就是为什么我没有投反对票的原因。=） - ninjagecko

Answer 3

您没有使用埃拉托斯特尼筛法; 不正确实现该算法的危险是它会变得极其缓慢。例如，尝试在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

- ninjagecko

---

我花了一些时间才明白，但这是一个非常聪明的实现。 - Parseltongue

谢谢，但功劳归于Eratosthenes =）：http://en.wikipedia.org/wiki/File:New_Animation_Sieve_of_Eratosthenes.gif 如果一个算法没有严格遵循这个形式，那么它很可能是错误的，因此非常慢。不幸的是，我省略了一个优化（为了可读性），即如果p > sqrt(upTo)，则停止划掉倍数。 - ninjagecko

Answer 4

这是目前我想到的最紧凑的真筛法。它的性能出奇的好。

def pgen(n): # Sieve of Eratosthenes generator
    np = set() # keeps track of composite (not prime) numbers
    for q in xrange(2, n+1):
        if q not in np:
            yield q
            np.update(range(q*q, n+1, q))

>>> list(pgen(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]            

这个稍微复杂一些的版本是我见过的最快的：

def pgen(n): # Sieve of Eratosthenes generator by Dan Salmonsen
    yield 2
    np = set()
    for q in xrange(3, n+1, 2):
        if q not in np:
            yield q
            np.update(range(q*q, n+1, q+q))            

这里是一个真正的筛子作为列表推导式：

def primes(n):
    sieve = set(sum([range(q*q, n+1, q+q) for q in odds], []))
    return [2] + [p for p in odds if p not in sieve]

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

- dansalmo

Answer 5

下面这个一行代码与你的代码完全无关：

def primes(n):
    return set(range(2,n))-{c for i in range(2,n) for c in range(2*i,n,i)}

就像你的代码一样，这仍然不是真正的埃拉托斯特尼筛法，因为例如它会徒劳地尝试划掉6和9等的倍数。尽管如此，在小于一百万或更多的值时，它仍然比大多数其他类似筛子的筛法运行得快得多，因为对于小的N，素数与非素数的数量“大约相同”（小于N的数字中是素数的比例是1/log(N)）。

从源代码进行了大量修改，可能不如原始版本高效：http://codeblog.dhananjaynene.com/2011/06/10-python-one-liners-to-impress-your-friends/

- ninjagecko

Answer 6

这是一个筛子的简单演示。请注意，我们没有使用 lambda 作为过滤函数，因为质数需要在定义时进行绑定。另外，该算法的效率在不重复除法方面非常高，但从长远来看，可能导致 某些问题。

import itertools

def primes():
    ints = itertools.count(2)
    while True:
        p = next(ints)
        yield p
        ints = itertools.ifilter(p.__rmod__, ints)

print list(itertools.islice(primes(), 10))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

- A. Coady

Answer 7

def sieve(n):
    sieve_list = range(n)
    zero_list = [0] * n
    for i in range(2, int(n**.5) + 1):
        if sieve_list[i]:
            sieve_list[2*i:n:i] = zero_list[2*i:n:i]
    return filter(None, sieve_list)[1:]

- sampwing

Answer 8

这并不是最紧凑的解决方案，但Python3中range函数中的步骤参数在这里很有帮助 -

prime_sieve = [True] * (int(input('Primes Upto ?'))+1)
# The first prime number
for i in range(2, len(prime_sieve)):
    if prime_sieve[i]:
        for j in range(i+i, len(prime_sieve), i):
            prime_sieve[j] = False
        print(i, end=',')

- aathif