Python 3:为什么我的素筛速度这么慢？
我在Python 3中实现了Eratosthenes的筛子，如下所示：
def sieve_of_eratosthenes(n):
is_prime = [True] * (n+1)
is_prime[0] = False
is_prime[1] = False
p = 0
while True:
for i, prime in enumerate(is_prime):
if prime and i > p:
p = i
break
else:
break
multiple = p + p
while multiple <= n:
is_prime[multiple]= False
multiple = multiple + p
r = []
for i, prime in enumerate(is_prime):
if prime: r.append(i)
return r运行这个到100,000需要25秒。
我觉得这太慢了，所以我决定采取另一种方法。筛子的工作前景很好:它可以清除所有倍数。我做了一个回顾性的工作，试着把所有的东西都分割得比现在的主要候选人低：
def retrospect(n):
primes = [2, 3]
i = 5
while i <= n:
isprime = True
lim = math.sqrt(n)+1
for p in primes:
if p > lim:
break
if i % p == 0:
isprime = False
break
if isprime:
primes.append(i)
i += 2
return primes我是快多了！
问题：
- 筛网的实施有什么明显的缺点吗？
- 回顾是否有比筛子慢的点？
回答 3
Code Review用户
发布于 2018-07-18 11:27:00
while True: for i, prime in enumerate(is\_prime): if prime and i > p: p = i break else: break
这是导致缓慢的原因:跟踪循环之间的状态，然后25秒下降到0.05秒。
multiple = p + p while multiple <= n: is\_prime[multiple]= False multiple = multiple + p
在这里使用range可能更像Pythonic：
for multiple in range(p + p, n + 1, p):
is_prime[multiple] = False当处理较大的输入时，从p * p开始而不是从p + p开始就变得有意义了(因为p的每一个比p * p小的复合倍数也有一个较小的素因子)。
r = [] for i, prime in enumerate(is\_prime): if prime: r.append(i) return r
国际海事组织更有意义的是将其嵌入主回路中。
此时编辑的代码：
def sieve_of_eratosthenes(n):
is_prime = [True] * (n+1)
is_prime[0] = False
is_prime[1] = False
primes = []
for p in range(2, n+1):
if is_prime[p]:
primes.append(p)
for multiple in range(p * p, n + 1, p):
is_prime[multiple] = False
return primes现在，如果你想要更快的速度，而不想让事情变得如此复杂，你可以通过特殊的外壳来应用一个简单的轮子--这是唯一的偶数：
def sieve_of_eratosthenes(n):
is_prime = [True] * (n+1)
primes = [2]
for p in range(3, n + 1, 2):
if is_prime[p]:
primes.append(p)
for multiple in range(p * p, n + 1, p + p):
is_prime[multiple] = False
return primesCode Review用户
发布于 2018-07-19 07:23:04
@Edward:修正极限
def sieve_of_eratosthenes(n):
is_prime = [False, True] * int(n/2 + 1)
n_plus_one = n + 1 # save n+1 for later use
del is_prime[n_plus_one:] #
is_prime[1] = False
is_prime[2] = True
#limit = int(math.sqrt(n))
limit = int(n**.5) + 1 # import math not required, limit corrected!
for i in range(3, limit):
if is_prime[i]:
for j in range(i*i, n_plus_one, 2*i): # limit corrected!
is_prime[j] = False
r = []
for i, prime in enumerate(is_prime):
if prime:
r.append(i)
return r如果没有修正的限制，s_o_e(9)产量2,3,5,7,9，那么9将是素数(以及11,13,17，.)
Code Review用户
发布于 2018-07-19 13:36:11
当然，在性能方面，使用numpy数组可以使计算速度提高10倍。
使用爱德华的代码来提高性能，同时使用以下代码(适应于numpy的“Edward1”算法)：
def sieve_of_eratosthenes(n):
import numpy as np
is_prime = np.ones(n,dtype=bool)
is_prime[0:2] = False
limit = int(math.sqrt(n))+1
for i in range(2, limit):
if is_prime[i]:
is_prime[np.arange(i*i,n,i)] = False
r = np.where(is_prime == True)[0]
return r我上了我的机器
https://codereview.stackexchange.com/questions/199734
复制相似问题
腾讯云开发者
