相关疑难解决方法(0)

这是我能提出的最佳算法.

def get_primes(n):
    numbers = set(range(n, 1, -1))
    primes = []
    while numbers:
        p = numbers.pop()
        primes.append(p)
        numbers.difference_update(set(range(p*2, n+1, p)))
    return primes

>>> timeit.Timer(stmt='get_primes.get_primes(1000000)', setup='import   get_primes').timeit(1)
1.1499958793645562

可以做得更快吗？

此代码有一个缺陷:由于numbers是无序集,因此无法保证numbers.pop()从集中删除最小数字.然而,它对某些输入数字起作用(至少对我而言):

>>> sum(get_primes(2000000))
142913828922L
#That's the correct sum of all numbers below 2 million
>>> 529 in get_primes(1000)
False
>>> 529 in get_primes(530)
True

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

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