blocks|key|166557|text|您可以进行许多优化(而且应该这样做，因为对于project+Euler中的许多问题，您将需要素数生成，因此拥有一个快速的实现可以简化以后的工作)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|166558|看一看Atkin的筛子(以及相关的筛子)+(http://en.wikipedia.org/wiki/Sieve_of_Atkin)，以了解如何通过蛮力(即算法)来加速素数生成。|offset|length|166559|然后看看对这篇S.O.-post+(Fastest+way+to+list+all+primes+below+N)的精彩回答，它记录了许多素数生成算法/实现。|166560|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Sieve_of_Atkin|1|https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python^0|0|M|17|0|0|I|12|1|0^^$0|@$1|2|3|4|5|6|7|R|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|S|8|@]|9|@$D|T|E|U|1|V]]|A|$]]|$1|F|3|G|5|6|7|W|8|@]|9|@$D|X|E|Y|1|Z]]|A|$]]|$1|H|3|-4|5|6|7|10|8|@]|9|@]|A|$]]]|I|$J|$5|K|L|M|A|$N|O]]|P|$5|K|L|M|A|$N|Q]]]]

There are many optimisations that you could do (and should do since you will need prime generation for many of the problems in project Euler, so having a fast implementation simplifies things later on). 

Take a look at the sieve of Atkin (and related sieves) (<a href="http://en.wikipedia.org/wiki/Sieve_of_Atkin" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Sieve_of_Atkin</a>) to get an understanding of how prime generation can be speeded up over brute force (algorithmically that is). 

Then take a look at the awesome answer to this S.O.-post (<a href="https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python">Fastest way to list all primes below N</a>) that clocks a number of prime generation algorithms/implementations.

blocks|key|164258|text|你的算法使用试除法，这是非常慢的。一种更好的算法是使用Eratosthenes筛子：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|164259|def+sumPrimes(n):
++++sum,+sieve+=+0,+[True]+*+n
++++for+p+in+range(2,+n):
++++++++if+sieve[p]:
++++++++++++sum+%2B=+p
++++++++++++for+i+in+range(p*p,+n,+p):
++++++++++++++++sieve[i]+=+False
++++return+sum

print+sumPrimes(2000000)|code-block|syntax|javascript|164260|这应该会在不到一秒的时间内运行。如果你对质数编程感兴趣，我在我的博客中谦虚地推荐这个essay。|offset|length|164261|entityMap|0|LINK|mutability|MUTABLE|url|http://programmingpraxis.com/essays^0|0|0|16|5|0|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|T|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|U|8|@]|9|@$I|V|J|W|1|X]]|A|$]]|$1|K|3|-4|5|6|7|Y|8|@]|9|@]|A|$]]]|L|$M|$5|N|O|P|A|$Q|R]]]]

Your algorithm uses trial division, which is very slow. A better algorithm uses the Sieve of Eratosthenes:

<pre><code>def sumPrimes(n):
 sum, sieve = 0, [True] * n
 for p in range(2, n):
 if sieve[p]:
 sum += p
 for i in range(p*p, n, p):
 sieve[i] = False
 return sum

print sumPrimes(2000000)
</code></pre>

That should run in less than a second. If you're interested in programming with prime numbers, I modestly recommend this <a href="http://programmingpraxis.com/essays" rel="noreferrer">essay</a> at my blog.

blocks|key|5026123|text|没有人指出这一点，但是在Python2.x中使用range非常慢。使用xrange+instaed，在这种情况下，这应该会给你带来巨大的性能优势。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|5026124|请参阅this+question.|5026125|此外，您不必循环，直到您检查的数字，检查直到round(sqrt(n))+%2B+1是足够的。(如果大于它的平方的数字除以它，那么您一定已经注意到有一个比平方更小的数字。)|5026126|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/questions/135041/should-you-always-favor-xrange-over-range^0|O|5|Z|6|0|3|E|0|0|M|I|0^^$0|@$1|2|3|4|5|6|7|R|8|@$9|S|A|T|B|C]|$9|U|A|V|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|W|8|@]|D|@$9|X|A|Y|1|Z]]|E|$]]|$1|H|3|I|5|6|7|10|8|@$9|11|A|12|B|C]]|D|@]|E|$]]|$1|J|3|-4|5|6|7|13|8|@]|D|@]|E|$]]]|K|$L|$5|M|N|O|E|$P|Q]]]]

Nobody pointed this out, but using <code>range</code> in Python 2.x is very slow. Use <code>xrange</code> instaed, in this case this should give you a huge performance advantage. 
See <a href="https://stackoverflow.com/questions/135041/should-you-always-favor-xrange-over-range">this question.</a>

Also, you don't have to loop until the number you check, checking until <code>round(sqrt(n)) + 1</code> is sufficient. (If the number greater than its square divides it, there's a number smaller than the square that you must have already noticed.)

blocks|key|164185|text|首先，你循环了太多的数字。你不需要检查每个小于给定数的数是否是除数来检查一个数是否是质数(我会让你弄清楚为什么这是你自己的)。你正在运行数千亿个循环，其中数亿个循环就足够了。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|164186|像这样的东西运行得更快，但绝不是最优的：|164187|++++value=2
++++for+i+in+range(3,+2000000):
++++++++prime=True+
++++++++if+i%252+!=+0:
++++++++++++for+j+in+range(3,+int(round(sqrt(i)%2B1)),2):
++++++++++++++++if+i+%25+j==0:
++++++++++++++++++++prime=False
++++++++else:
++++++++++++prime=False
++++++++if+prime==True:
++++++++++++value%2B=i
++++print+value|code-block|syntax|javascript|164188|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|L|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|M|8|@]|9|@]|A|$G|H]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

First off, you're looping over too many numbers. You don't need to check if EVERY number less than a given number is a divisor to check if a number is prime (I'll let you figure out why this is yourself). You are running hundreds of billions of loops, where hundreds of millions will do.

Something like this works faster, but is by no means optimal:

<pre><code> value=2
 for i in range(3, 2000000):
 prime=True 
 if i%2 != 0:
 for j in range(3, int(round(sqrt(i)+1)),2):
 if i % j==0:
 prime=False
 else:
 prime=False
 if prime==True:
 value+=i
 print value
</code></pre>

blocks|key|2072701|text|您需要使用质数筛子，签出eratostheneses筛子，并尝试在代码中实现它。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2072702|试除法寻找素数的效率非常低，因为它的复杂度是n平方，运行时间增长非常快。这个任务的目的是教你如何找到更好的东西。|2072703|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

You need to use prime sieve check out eratostheneses sieve and try to implement it in code. 

Trial division is very inefficient for finding primes because it has complexity n square, the running time grows very fast. This task is meant to teach you how to find something better.

blocks|key|2072791|text|首先，我认为你可以通过定义一个函数来拆分代码。然而，在这种情况下使用常规函数有一个缺点，因为每次常规函数return一个值时，对该函数的下一次调用将再次执行函数内部的完整代码。既然你要迭代两百万次，最好是：|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|2072792|2072793|有一个函数，它提供下一个质数，并暂时将控制权返回给调用者。这样的函数称为GENERATORS.|unordered-list-item|2072794|To定义生成器函数只需使用yield命令而不是return.|2072795|When您使用生成器，就像知道函数将再次被调用一样，当发生这种情况时，函数内部的执行将在yield指令之后继续执行，而不是再次遍历整个函数。|2072796|这种方法的优点是，在迭代器的长期运行中，您可以避免消耗系统的所有内存。|2072797|2072798|我建议你去看看this+article+about+generators+in+python。它为这个例子提供了更广泛的解释。|2072799|解决方案应该是这样的：|2072800|import+math

#+Check+if+a+number+is+prime
def+is_prime(number):
++++if+number+>+1:
++++++++if+number+==+2:
++++++++++++return+True
++++++++if+number+%25+2+==+0:
++++++++++++return+False
++++++++for+current+in+range(3,+int(math.sqrt(number)+%2B+1),+2):
++++++++++++if+number+%25+current+==+0:+
++++++++++++++++return+False
++++++++return+True
++++return+False

#+Get+the+next+after+a+given+number
def+get_primes(number):
++++while+True:
++++++++if+is_prime(number):
++++++++++++yield+number
++++++++#+Next+call+to+the+function+will+continue+here!+++
++++++++number+%2B=+1+

#+Get+the+sum+of+all+prime+numbers+under+a+number
def+sum_primes_under(limit):
++++total+=+2
++++for+next_prime+in+get_primes(3):
++++++++if+next_prime+<+limit:
++++++++++++total+%2B=+next_prime
++++++++else:
++++++++++++print(total)
++++++++++++return

#+Call+the+function
sum_primes_under(2000000)|code-block|syntax|javascript|2072801|entityMap|0|LINK|mutability|MUTABLE|url|https://www.python-course.eu/python3_generators.php|1|https://jeffknupp.com/blog/2013/04/07/improve-your-python-yield-and-generators-explained/^0|1G|6|0|0|10|A|0|0|D|5|N|6|0|18|5|0|0|0|7|13|1|0|0|0^^$0|@$1|2|3|4|5|6|7|19|8|@$9|1A|A|1B|B|C]]|D|@]|E|$]]|$1|F|3|-4|5|6|7|1C|8|@]|D|@]|E|$]]|$1|G|3|H|5|I|7|1D|8|@]|D|@$9|1E|A|1F|1|1G]]|E|$]]|$1|J|3|K|5|I|7|1H|8|@$9|1I|A|1J|B|C]|$9|1K|A|1L|B|C]]|D|@]|E|$]]|$1|L|3|M|5|I|7|1M|8|@$9|1N|A|1O|B|C]]|D|@]|E|$]]|$1|N|3|O|5|I|7|1P|8|@]|D|@]|E|$]]|$1|P|3|-4|5|6|7|1Q|8|@]|D|@]|E|$]]|$1|Q|3|R|5|6|7|1R|8|@]|D|@$9|1S|A|1T|1|1U]]|E|$]]|$1|S|3|T|5|6|7|1V|8|@]|D|@]|E|$]]|$1|U|3|V|5|W|7|1W|8|@]|D|@]|E|$X|Y]]|$1|Z|3|-4|5|6|7|1X|8|@]|D|@]|E|$]]]|10|$11|$5|12|13|14|E|$15|16]]|17|$5|12|13|14|E|$15|18]]]]

First of all, I think you can split your code by defining a function. However, there is a drawback of using a regular function in this case because every time a normal function <code>return</code> a value, the next call to the function will execute the complete code inside the function again. Since you are iterating 2 million times, it would be better to:

<ul>
<li>Have a function that gives you the next prime number and provisionally returns the control to the caller. Such functions are known as <a href="https://www.python-course.eu/python3_generators.php" rel="nofollow noreferrer">GENERATORS</a>.</li>
<li>To define a generator function just use the <code>yield</code> command instead of <code>return</code>.</li>
<li>When you use generators , it is like knowing that the function will be called again and when it happens the execution inside the function continues right after the <code>yield</code> instruction instead of going over the whole function again.</li>
<li>The advantage of this approach is that on the long run of an iterator you avoid the consumption all of the system's memory.</li>
</ul>

I recommend you to have a look at <a href="https://jeffknupp.com/blog/2013/04/07/improve-your-python-yield-and-generators-explained/" rel="nofollow noreferrer">this article about generators in python</a>. It provides a more extensive explanation for this example.

The solution would be something like this:

<pre><code>import math

# Check if a number is prime
def is_prime(number):
 if number &gt; 1:
 if number == 2:
 return True
 if number % 2 == 0:
 return False
 for current in range(3, int(math.sqrt(number) + 1), 2):
 if number % current == 0: 
 return False
 return True
 return False

# Get the next after a given number
def get_primes(number):
 while True:
 if is_prime(number):
 yield number
 # Next call to the function will continue here! 
 number += 1 

# Get the sum of all prime numbers under a number
def sum_primes_under(limit):
 total = 2
 for next_prime in get_primes(3):
 if next_prime &lt; limit:
 total += next_prime
 else:
 print(total)
 return

# Call the function
sum_primes_under(2000000)
</code></pre>

blocks|key|166616|text|当你使用eratosthenes+Link+to+it的筛子时，这个问题给出的输出非常快。你可以通过一些小的修改来使它更快，比如只考虑奇数将整个200万个数字迭代一半。这样你可以节省很多时间。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|166617|n+=+2000000
ar+=+[False+for+x+in+range(n)]
sum+=+2
def+mul(a):
++++i+=+2;p+=+i*a
++++while+(p+<+n):
++++++++ar[p]+=+1
++++++++%2B%2Bi
++++++++p+=+i*a
while+(x+<+n):
++++if(ar[x]+==+0):
++++++++sum+%2B=+x;mul(x)
++++x+%2B=+2
print+(sum)|code-block|syntax|javascript|166618|在这里你可以在c%2B%2B中看到相同的算法：|166619|#include<bits/stdc%2B%2B.h>
using+namespace+std;
const+int+n+=+2000000;
bool+ar[n];
void+mul(int+a)
{
++++int+i+=+2;int+p+=+i*a;
++++while(p+<+n)
++++{
++++++++ar[p]+=+1;
++++++++%2B%2Bi;p+=+i*a;
++++}
}
long+long+sieve()
{
++++long+long+sum+=+2;
++++for(int+i+=+3;i+<+n;i+%2B=+2)
++++{
++++++++if(ar[i]+==+0)
++++++++++++sum+%2B=+i,mul(i);
++++}
++++return+sum;
}
int+main()
{
++++cout<<sieve();
++++return+0;
}|166620|无论如何，C%2B%2B的运行速度比python快10倍左右，对于这个算法也是如此。|166621|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes^0|H|A|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|W|8|@]|9|@$A|X|B|Y|1|Z]]|C|$]]|$1|D|3|E|5|F|7|10|8|@]|9|@]|C|$G|H]]|$1|I|3|J|5|6|7|11|8|@]|9|@]|C|$]]|$1|K|3|L|5|F|7|12|8|@]|9|@]|C|$G|H]]|$1|M|3|N|5|6|7|13|8|@]|9|@]|C|$]]|$1|O|3|-4|5|6|7|14|8|@]|9|@]|C|$]]]|P|$Q|$5|R|S|T|C|$U|V]]]]

This question gives output quite very fast when you use sieve of eratosthenes <a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="nofollow">Link to it</a>. You can make it even more faster with a little modification like iterating the whole 2 million numbers just half times by considering only the odd numbers. This way you can save lots of time.

<pre><code>n = 2000000
ar = [False for x in range(n)]
sum = 2
def mul(a):
 i = 2;p = i*a
 while (p &lt; n):
 ar[p] = 1
 ++i
 p = i*a
while (x &lt; n):
 if(ar[x] == 0):
 sum += x;mul(x)
 x += 2
print (sum)
</code></pre>

Here you can see the same algorithm in c++:-

<pre><code>#include&lt;bits/stdc++.h&gt;
using namespace std;
const int n = 2000000;
bool ar[n];
void mul(int a)
{
 int i = 2;int p = i*a;
 while(p &lt; n)
 {
 ar[p] = 1;
 ++i;p = i*a;
 }
}
long long sieve()
{
 long long sum = 2;
 for(int i = 3;i &lt; n;i += 2)
 {
 if(ar[i] == 0)
 sum += i,mul(i);
 }
 return sum;
}
int main()
{
 cout&lt;&lt;sieve();
 return 0;
}
</code></pre>

C++ works around 10 times faster than python anyways and for this algorithm too.

blocks|key|166627|text|sum+=+2

def+isPrime(n):
++++if+n+%25+2+==+0:+return+False
++++for+i+in+range(3,+int(n**0.5)%2B1,+2):
++++++++if+n+%25+i+==+0:+return+False
++++return+True
if+__name__+==+"__main__":
++++n+=+1
++++while+n+<+2000000:
++++++++n+%2B=+2
++++++++if+isPrime(n):sum+%2B=+n
print+sum|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|166628|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>sum = 2

def isPrime(n):
 if n % 2 == 0: return False
 for i in range(3, int(n**0.5)+1, 2):
 if n % i == 0: return False
 return True
if __name__ == "__main__":
 n = 1
 while n &lt; 2000000:
 n += 2
 if isPrime(n):sum += n
print sum
</code></pre>

blocks|key|2912131|text|import+time
start+=+time.time()

def+is_prime(num):
++++prime+=+True
++++for+i+in+range(2,int(num**0.5)%2B1):
++++++++if+num+%25+i+==+0:
++++++++++++prime+=+False
++++++++++++break
++++return+prime
sum_prime+=+0
for+i+in+range(2,2000000):
++++if+is_prime(i):
++++++++sum_prime+%2B=+i
print("sum:+",sum_prime)

elapsed+=+(time.time()+-+start)
print("This+code+took:+"+%2B+str(elapsed)+%2B+"+seconds")|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|2912132|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>import time
start = time.time()

def is_prime(num):
 prime = True
 for i in range(2,int(num**0.5)+1):
 if num % i == 0:
 prime = False
 break
 return prime
sum_prime = 0
for i in range(2,2000000):
 if is_prime(i):
 sum_prime += i
print("sum: ",sum_prime)

elapsed = (time.time() - start)
print("This code took: " + str(elapsed) + " seconds")
</code></pre>

Why is my algorithm for finding the sum of all prime numbers below 2 million so slow?
I'm a fairly beginner programmer and this is what I came up with for finding the solution:

<pre><code>import time

sum = 2
start = time.time()

for number in range(3, 2000000):
 prime = True
 for x in range(2, number):
 if number % x == 0:
 prime = False
 if prime:
 sum += number

print "Sum =", sum
end = time.time() - start
print "Runtime =", end
</code></pre>

Can someone please help me out?
Thanks!

Project Euler #10 (Python)

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

为什么我的算法找出小于200万的所有质数的和是如此的慢？我是一个相当初级的程序员，这是我想出的解决方案：import timesum = 2start = time.time()for number in range(3, 2000000):    prime = True    for x in range(2, number):        if number % x == 0:      

问Project Euler #10 (Python)
EN

回答 9

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Project Euler #10 (Python)EN

回答 9

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Project Euler #10 (Python)
EN