这是我能提出的最佳算法.
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
我正在尝试欧拉计划的第 10 题，即 2,000,000 以下所有素数的总和。我尝试过使用 Python 实现埃拉斯托坦筛法，我编写的代码对于 10,000 以下的数字非常有效。
然而，当我尝试求更大数字的素数之和时，代码运行时间太长（求 100,000 以内的素数之和需要 315 秒）。该算法显然需要优化。
是的，我看过这个网站上的其他帖子，比如列出 N 以下所有素数的最快方法，但是那里的解决方案对代码如何工作的解释很少（我仍然是初学者程序员），所以我无法实际上向他们学习。
有人可以帮助我优化我的代码，并清楚地解释它是如何工作的吗？
这是我的代码：
primes_below_number = 2000000 # number to find summation of all primes below number
numbers = (range(1, primes_below_number + 1, 2)) # creates a list excluding even numbers
pos = 0 # index position
sum_of_primes = 0 # total sum
number = numbers[pos]
while number < primes_below_number and pos < len(numbers) - 1:
pos += 1
number = numbers[pos] # …也许这是一个愚蠢的问题,但我想知道你是否可以提供最短的来源,用Python找到素数.我还想知道如何使用map()或filter()函数找到素数.谢谢 (:
编辑:当我说最快/最短时,我指的是字符/单词较少的方式.无论如何,不要考虑比赛:我想知道是否有可能是单线源,而不会删除总是与周期一起使用的缩进.编辑2:没有想到大问题的问题.我认为我们可以保持在一百万以下(范围(2,1000000)编辑3:最短,但仍然优雅.正如我在第一次编辑中所说,你不需要将变量的名称减少为单个字母.我只需要一个一线,优雅的来源.谢谢!