筛法求素数表
第一个版本:
P=range(2,20001)
i=0
l=len(P)
t1=datetime.datetime.now()
while i
for item in P[(i+1):]:
if item % P[i]==0:
P.remove(item)
l-=1
i+=1
t2=datetime.datetime.now()
print t2-t1
print P
第二个版本:
P=range(2,20001)
i=0
l=len(P)
t1=datetime.datetime.now()
while i
temp=[item for item in P[(i+1):] if item % P[i] != 0]
P=P[:(i+1)]+temp
l=len(P)
i+=1
t2=datetime.datetime.now()
print t2-t1
print P
第三个版本:
temp=range(2,20001)
P=[]
t1=datetime.datetime.now()
while temp!=[]:
P.append(temp[0])
temp=[item for item in temp if item % P[-1] != 0]
t2=datetime.datetime.now()
print t2-t1
print P
第一个版本需要7秒多,第二个版本只需要2秒多,第三个版本就只需要1.8秒左右了。
注1:刚开始学Python,正在慢慢体会Python的精神,希望能尽快写出Python风格的程序,而不是用Python语言写Pascal程序。
注2:正是因为刚开始学,所以实际上不止三个版本,但是从7秒多优化到2秒以内,还是很有成就感的。
注3:还是太慢了。
发现一个更快(非常快)的版本:
""” returns a list of prime numbers from 2 to < n “”"
if n < 2: return []
if n == 2: return [2]
# do only odd numbers starting at 3
s = range(3, n, 2)
# n**0.5 may be slightly faster than math.sqrt(n)
mroot = n ** 0.5
half = len(s)
i = 0
m = 3
while m <= mroot:
if s[i]:
j = (m * m – 3)//2
s[j] = 0
while j < half:
s[j] = 0
j += m
i = i + 1
m = 2 * i + 3
# make exception for 2
return [2]+[x for x in s if x]
amao
14 10 08 at 10:42 下午
还是换一种语言提升的效率更多
比如用c语言,生成2000000以内的素数表只用2s不到
vilinov
17 10 08 at 2:06 下午