最快的空间 - 用python查找素数

Question

也许这是一个愚蠢的问题,但我想知道你是否可以提供最短的来源,用Python找到素数.我还想知道如何使用map()或filter()函数找到素数.谢谢 (:

编辑:当我说最快/最短时,我指的是字符/单词较少的方式.无论如何,不​​要考虑比赛:我想知道是否有可能是单线源,而不会删除总是与周期一起使用的缩进.编辑2:没有想到大问题的问题.我认为我们可以保持在一百万以下(范围(2,1000000)编辑3:最短,但仍然优雅.正如我在第一次编辑中所说,你不需要将变量的名称减少为单个字母.我只需要一个一线,优雅的来源.谢谢!

Answer 1

Eratosthenes的筛子有两条线.

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

编辑:我已经意识到上面不是真正的Eratosthenes筛子,因为它过滤了一组奇数而不是素数集,使得它不必要地变慢.我在以下版本中修复了它,并且还包括了一些常见的优化,如评论中所指出的那样.

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

第一个版本仍然更短,并且确实产生了正确的结果,即使它需要更长的时间.