[其他] 求素数
 |
ipython
2009-02-07
import math
l=[]
for i in range(1,20000,2):
f=0
k=math.sqrt(i)
for j in range(2,k+1,1):
if i%j==0:
f=0
break
else:
f=1
if f==1:
print i
l.append(i)
这样的代码怎样才能优化?
|
 |
harry
2009-02-09
该用更好的算法
|
 |
lin_llx
2009-02-16
好方法就是打表。。从2开始到n，把质数的所有倍数去掉。。。
|
|
lin_llx
2009-02-16
当然可以用range函数做优化，比如xrange(a,b,c*2)，c是当前的质数。。
|
 |
mermei
2010-09-06
该用更好的算法
ist=[i for i in range(3,s,2) if 0 not in [i%d for d in range(3,i-1)]] |
|
mermei
2010-09-06
上面那个耗时，下面这个还有请大家指点：
N=[] L=[i for i in range(3,s,2)] while L: N.append(L.pop(0)) for i in L: if i%N[-1]==0:L.remove(i) N.insert(0,2) |
