[已解决]如何优化素数生成器求和

亘川锌酸猫

刚开始学零基础python，做生成器课后作业，代码可以正确计算2,000,000以内所有素数的和，但是用时极长，运行了500多秒，非常没有效率。
目测是因为随着找到素数的数量增加，计算量也指数上涨。

要怎么改进才能提升效率？还是说这种计算方法本身就过于繁琐，不适合用来生成素数？

代码：

1. def prime_seq():
   
2.     prime_list = [2, 3]
   
3.     yield 2
   
4.     yield 3
   
5.     i = 3
   
6.     while True:
   
7.         i += 2
   
8.         for each_prime in prime_list:
   
9.             if i % each_prime == 0:
   
10.                 break
    
11.         else:
    
12.             prime_list.append(i)
    
13.             yield i
    
14. 
    
15. 
    
16. sum_of_primes = 0
    
17. # 这里用一个计时器简单记录跑代码的时间
    
18. start_time = time.time()
    
19. for each in prime_seq():
    
20.     if each < 2000000:
    
21.         sum_of_primes += each
    
22.     else:
    
23.         print(sum_of_primes)
    
24.         end_time = time.time()
    
25.         print('Run time: %.4f' %(end_time - start_time))
    
26.         break

复制代码

最佳答案

月排行榜 / 总排行榜

TJBEST

2020-4-6 17:29:25

你看看这结果对吗？

1. import time
   
2. def SieveOfEratosthenes(n):
   
3.     prime = [True for i in range(n+1)]
   
4.     p = 2
   
5.     while p * p <= n:
   
6.         if (prime[p] == True):
   
7.             for i in range(p * 2, n + 1, p):
   
8.                 prime[i] = False
   
9.         p += 1
   
10.     for index in range(2,n+1):
    
11.         if prime[index]:
    
12.             yield index
    
13. def prime_seq():
    
14.     return SieveOfEratosthenes(2005000)
    
15. sum_of_primes = 0
    
16. # 这里用一个计时器简单记录跑代码的时间
    
17. start_time = time.time()
    
18. for each in prime_seq():
    
19.     if each < 2000000:
    
20.         sum_of_primes += each
    
21.     else:
    
22.         print(sum_of_primes)
    
23.         end_time = time.time()
    
24.         print('Run time: %.4f' %(end_time - start_time))
    
25.         break

复制代码

跳转到最佳答案楼层

BngThea

用sum函数一次性求和

亘川锌酸猫

BngThea 发表于 2020-4-6 14:43
用sum函数一次性求和

刚去尝试了一下，并没有变快。我怀疑是生成器不够优化的问题。

TJBEST

你的素数求法不是最优解，我给你一个方法，保证提高速度，17:30奉上答案，及得采纳哦，好了我去写了

zltzlt

不知道这个够不够快

1. import time
   
2. 
   
3. 
   
4. def is_prime(n):
   
5.     return True if n in {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67} else all(
   
6.         False for p in {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67} if
   
7.         pow(p, n - 1, n) != 1)
   
8. 
   
9. 
   
10. def prime_seq():
    
11.     yield 2
    
12.     yield 3
    
13.     i = 3
    
14.     while True:
    
15.         i += 2
    
16.         if is_prime(i):
    
17.             yield i
    
18. 
    
19. 
    
20. sum_of_primes = 0
    
21. # 这里用一个计时器简单记录跑代码的时间
    
22. start_time = time.time()
    
23. for each in prime_seq():
    
24.     if each < 2000000:
    
25.         sum_of_primes += each
    
26.     else:
    
27.         print(sum_of_primes)
    
28.         end_time = time.time()
    
29.         print('Run time: %.4f' % (end_time - start_time))
    
30.         break

复制代码

永恒的蓝色梦想

1. def func(end):
   
2.     primelist=[True]*(end+1)
   
3.     primelist[0]=primelist[1]=False
   
4.     for i,prime in enumerate(primelist[:end>>1]):
   
5.         if prime:
   
6.             for j in range(2*i,end+1,i):
   
7.                 primelist[j]=False
   
8.     return sum((i for i,prime in enumerate(primelist) if prime))
   
9. 
   
10. print(func(2000000))

复制代码

素数筛法

TJBEST

你看看这结果对吗？

1. import time
   
2. def SieveOfEratosthenes(n):
   
3.     prime = [True for i in range(n+1)]
   
4.     p = 2
   
5.     while p * p <= n:
   
6.         if (prime[p] == True):
   
7.             for i in range(p * 2, n + 1, p):
   
8.                 prime[i] = False
   
9.         p += 1
   
10.     for index in range(2,n+1):
    
11.         if prime[index]:
    
12.             yield index
    
13. def prime_seq():
    
14.     return SieveOfEratosthenes(2005000)
    
15. sum_of_primes = 0
    
16. # 这里用一个计时器简单记录跑代码的时间
    
17. start_time = time.time()
    
18. for each in prime_seq():
    
19.     if each < 2000000:
    
20.         sum_of_primes += each
    
21.     else:
    
22.         print(sum_of_primes)
    
23.         end_time = time.time()
    
24.         print('Run time: %.4f' %(end_time - start_time))
    
25.         break

复制代码

TJBEST

好吧，你要的是生成器，我可以改成一个无限素数的生成器，稍等。

亘川锌酸猫

TJBEST 发表于 2020-4-6 17:29
你看看这结果对吗？

感谢帮助，容我慢慢品一品

亘川锌酸猫

永恒的蓝色梦想 发表于 2020-4-6 17:25
素数筛法

感谢！容我理解学习一下

TJBEST

亘川锌酸猫 发表于 2020-4-6 17:39
感谢帮助，容我慢慢品一品

我觉得这个更符合你的要求。可以无限输出，手动break
核心思想 假设：一个正整数n>4 且 正整数m满足2<m < n 。命题' m是合数' 等价于命题'存在一个质数p，满足 p <=根号（n）能够整除m'

1. import math
   
2. import time
   
3. def prime_seq():
   
4.     prime = [True for i in range(1000000 + 1)]
   
5.     jilu = set()
   
6.     p = 2
   
7.     #第一次遍历
   
8.     while p * p <= 1000000:
   
9.         if (prime[p] == True):
   
10.             for i in range(p * 2, 1000000 + 1, p):
    
11.                 prime[i] = False
    
12.         p += 1
    
13.     for index in range(2,1000000+1):
    
14.         if prime[index]:
    
15.             jilu.add(index)
    
16.             yield index
    
17.     prime = [True for i in range(1000000)]
    
18.     page = 1
    
19.     while True:
    
20.         offset = 1000000*page + 1
    
21.         end = 1000000 * (page + 1)
    
22.         #第page+1次遍历
    
23.         firstGate = math.floor(end**(1/2))
    
24.         for p  in jilu :
    
25.             if p > firstGate:
    
26.                 continue
    
27.             firstRes = offset % p
    
28.             fisrtPosition = (p - firstRes)%p
    
29.             for i in range(fisrtPosition,1000000,p):
    
30.                 prime[i] = False
    
31.         for index in range(0,1000000):
    
32.             if prime[index]:
    
33.                 jilu.add(offset + index)
    
34.                 yield offset + index
    
35.         page += 1
    
36.         prime = [True for i in range(1000000)]
    
37. sum_of_primes = 0
    
38. # 这里用一个计时器简单记录跑代码的时间
    
39. start_time = time.time()
    
40. for each in prime_seq():
    
41.     if each < 2000000:
    
42.         sum_of_primes += each
    
43.     else:
    
44.         print(sum_of_primes)
    
45.         end_time = time.time()
    
46.         print('Run time: %.4f' %(end_time - start_time))
    
47.         break

复制代码