改进Euler #10的运行时
改进Euler #10的运行时
提问于 2014-11-03 18:22:47
所以我攻击了一个Euler问题，这个问题在小范围内看起来很简单，但是一旦我把它增加到我应该做的数目，代码就会永远运行。这就是问题所在：
低于10的素数之和为2+3+5+7= 17。 找出二百万以下所有素数的总和。
我用Python做的。我可以等几个小时代码才能运行，但我更希望找到一种更有效的方法来实现这一点。下面是Python中的代码：
x = 1;
total = 0;
while x <= 2000000:
y = 1;
z = 0;
while x >= y:
if x % y == 0:
z += 1;
y += 1;
if z == 2:
total += x
x += 1;
print total;回答 2
Stack Overflow用户
回答已采纳
发布于 2014-11-03 18:51:15
正如评论中提到的，实施Eratosthenes筛子将是一个更好的选择。在这种情况下，它占用了O(n)额外的空间，这是一个长度约为200万的数组。它还运行在O(n)中，这比在O(n²)中运行的实现要快得多。
我最初是用JavaScript编写这篇文章的，所以请容忍我的python：
max = 2000000 # we only need to check the first 2 million numbers
numbers = []
sum = 0
for i in range(2, max): # 0 and 1 are not primes
numbers.append(i) # fill our blank list
for p in range(2, max):
if numbers[p - 2] != -1: # if p (our array stays at 2, not 0) is not -1
# it is prime, so add it to our sum
sum += numbers[p - 2]
# now, we need to mark every multiple of p as composite, starting at 2p
c = 2 * p
while c < max:
# we'll mark composite numbers as -1
numbers[c - 2] = -1
# increment the count to 3p, 4p, 5p, ... np
c += p
print(sum)这里唯一令人困惑的地方可能是我为什么使用numbers[p - 2]。这是因为我跳过了0和1，这意味着2在索引0。换句话说，所有的东西都被两个指数移到了一边。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/26726722
复制相关文章
相似问题
添加站长 进交流群
领取专属 10元无门槛券
AI混元助手 在线答疑
关注 腾讯云开发者公众号
洞察 腾讯核心技术
剖析业界实践案例
腾讯云开发者
