我正在尝试欧拉计划的第 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] # moves to next prime in list numbers
sum_of_primes += number # adds prime to total sum
num = number
while num < primes_below_number:
num += number
if num in numbers[:]:
numbers.remove(num) # removes multiples of prime found
print sum_of_primes + 2
正如我之前所说,我是编程新手,因此对任何复杂概念的彻底解释将不胜感激。谢谢。
正如您所看到的,有多种方法可以在 Python 中实现埃拉斯托滕筛法,这些方法比您的代码更有效。我不想用花哨的代码让您感到困惑,但我可以展示如何加快您的代码的速度。
首先,搜索列表并不快,从列表中删除元素甚至更慢。然而,Python 提供了一个集合类型,它在执行这两个操作时非常有效(尽管它确实比简单列表消耗更多的 RAM)。令人高兴的是,可以轻松修改代码以使用集合而不是列表。
另一个优化是我们不必一直检查素因数primes_below_number
,我已将其重命名为hi
在下面的代码中。只需求平方根就足够了hi
,因为如果一个数是合数,则它的因数必须小于或等于其平方根。
我们不需要保存素数之和的运行总和。最好最后使用 Python 的内置函数来完成此操作sum()
函数以 C 速度运行,因此它比以 Python 速度逐一进行加法要快得多。
# number to find summation of all primes below number
hi = 2000000
# create a set excluding even numbers
numbers = set(xrange(3, hi + 1, 2))
for number in xrange(3, int(hi ** 0.5) + 1):
if number not in numbers:
#number must have been removed because it has a prime factor
continue
num = number
while num < hi:
num += number
if num in numbers:
# Remove multiples of prime found
numbers.remove(num)
print 2 + sum(numbers)
您应该会发现这段代码在几秒钟内运行;在我的 2GHz 单核机器上大约需要 5 秒。
您会注意到我已经移动了评论,以便它们位于正在评论的行上方。这是 Python 中的首选样式,因为我们更喜欢短行,而且内联注释往往会使代码看起来混乱。
还有一个可以对内部进行的小优化while
循环,但我让你自己弄清楚。 :)
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)