用Python寻找质数的最快空间效率方法

Question

也许这个问题有点傻，但我想知道有没有最简单的Python代码来找出质数。我还想了解一下如何用map()或filter()函数来找质数。谢谢你（:

编辑：我说的最快/最短是指字符或单词最少的方式。别把这当成比赛，我只是想知道有没有可能用一行代码来实现，而且不想去掉for循环常用的缩进。
编辑2：这个问题不是针对很大的数字。我觉得我们可以限制在一百万以内（range(2,1000000)）。
编辑3：要尽量简短，但也要优雅。正如我在第一次编辑中说的，你不需要把变量名缩减成单个字母。我只需要一行优雅的代码。谢谢！

Answer 1

和上面提到的类似，但没有罗伯特·金的回答那么调皮：

from itertools import ifilter, imap
def primes(max=3000):
    r = set(); [r.add(n) for n in ifilter(lambda c: all(imap(c.__mod__, r)), xrange(2, max+1))]; return sorted(r)

Answer 2

因为你可以直接从网上复制前一百万个质数：

map(int,open('primes.txt'))

这和我昨天问的一个问题有点像，wim给了一个相对简短的回答：

这个质数生成器的写法算不算Python风格

Answer 3

埃拉托斯特尼筛法的简单介绍，只有两行代码。

primes = set(range(2,1000000))
for n in [2]+range(3,1000000/2,2): primes -= set(range(2*n,1000000,n))

补充说明：我意识到上面的代码并不是真正的埃拉托斯特尼筛法，因为它是基于奇数来筛选，而不是基于质数，这样会让它变得不必要的慢。我在下面的版本中修正了这个问题，并且根据评论中提到的内容加入了一些常见的优化。

primes = set([2] + range(3, 1000000, 2))
for n in range(3, int(1000000**0.5)+1, 2): primes -= set(range(n*n,1000000,2*n) if n in primes else [])

第一版的代码虽然更短，虽然运行时间较长，但仍然能产生正确的结果。