[已解决]049讲生成器动动手计算2000000以内的素数之和【运行速度爆了】

teribsandy

代码1:小甲鱼标答 ——运行时间9.7s

1. import math
   
2. 
   
3. def is_prime(number):
   
4.     if number > 1:
   
5.         if number == 2:
   
6.             return True
   
7.         if number % 2 == 0:
   
8.             return False
   
9.         for current in range(3, int(math.sqrt(number) + 1), 2):
   
10.             if number % current == 0:
    
11.                 return False
    
12.         return True
    
13.     return False
    
14. 
    
15. def get_primes(number):
    
16.     while True:
    
17.         if is_prime(number):
    
18.             yield number
    
19.         number += 1
    
20. 
    
21. def solve():
    
22.     total = 2
    
23.     for next_prime in get_primes(3):
    
24.         if next_prime < 2000000:
    
25.             total += next_prime
    
26.         else:
    
27.             print(total)
    
28.             return
    
29. 
    
30. if __name__ == '__main__':
    
31.     solve()

复制代码

代码2:相比小甲鱼的代码1，我求的是20000以内的素数和，运行时间都要11.7s

1. def is_prime(number):
   
2.         status=0
   
3.         if number==1:
   
4.                 status=1
   
5.         if number==2:
   
6.                 status=0
   
7.         if number>2:
   
8.                 for each in xrange(2,number):
   
9.                         if number%each==0:
   
10.                                 status=1
    
11.         return status #status=0说明是素数
    
12. 
    
13. def get_prime(target):
    
14.         num=target-1
    
15.         while num:
    
16.                 if is_prime(num)==0:
    
17.                         yield num
    
18.                 num-=1
    
19. def total_prime(target):
    
20.         a=get_prime(target)
    
21.         total=0
    
22.         for each in a:
    
23.                 total+=each
    
24.         return total
    
25. 
    
26. print total_prime(20000)

复制代码

代码3: 这个也是求的20000以内的，运行速度还不如代码2了....我都不愿意等下去了.....

1. def is_prime(number):
   
2.         status=0
   
3.         if number==1:
   
4.                 status=1
   
5.         if number==2:
   
6.                 status=0
   
7.         if number>2:
   
8.                 for each in xrange(2,number):
   
9.                         if number%each==0:
   
10.                                 status=1
    
11.         return status #status=0说明是素数
    
12. 
    
13. def get_prime(num):
    
14.         while True:
    
15.                 if is_prime(num)==0:
    
16.                         yield num
    
17.                 num+=1
    
18. 
    
19. def total_prime(target):
    
20.         a=get_prime(1)
    
21.         total=0
    
22.         for each in a:
    
23.                 if each<2000000:
    
24.                         total+=each
    
25.         return total
    
26. print total_prime(20000)

复制代码

想请问一下，这几个代码同样都是用的生成器，为什么运行速度差这么多，差在哪了呢？如何才能提高代码的运行速度？谢谢～～～～

最佳答案

月排行榜 / 总排行榜

Luke李

2018-4-15 10:45:54

差距是在判断是否是素数的算法上，举个例子，从10000到20000，你的算法差不多算了（10000+20000）*10000/2 次，而小甲鱼的只需要差不多运算（100+142）*42/2 次左右，这里差了将近150，000，000次运算，所以算的很慢。
要想提高这道题代码的运行速度，我认为还是要在判断素数的算法上去解决，你可以像小甲鱼那样只遍历到sqrt，或者更优化你可以将从小到大的素数都保存下来，只遍历sqrt以下的素数，这样会更快。

跳转到最佳答案楼层

Luke李

差距是在判断是否是素数的算法上，举个例子，从10000到20000，你的算法差不多算了（10000+20000）*10000/2 次，而小甲鱼的只需要差不多运算（100+142）*42/2 次左右，这里差了将近150，000，000次运算，所以算的很慢。
要想提高这道题代码的运行速度，我认为还是要在判断素数的算法上去解决，你可以像小甲鱼那样只遍历到sqrt，或者更优化你可以将从小到大的素数都保存下来，只遍历sqrt以下的素数，这样会更快。