python寻找第k个素数

Life is short, you need Python - Bruce Eckel
Package Index, Python 3.5.3 documentation
回复
happy886rr
渐入佳境
渐入佳境
帖子: 45
注册时间: 2016年09月27日 16:11
联系:

python寻找第k个素数

帖子 happy886rr »

在python中分片的扩展形式:str[I:J:K]意思是从I到J-1,每隔K个元素索引一次,如果K为负数,就是按从右往左索引。用这个分片函数,就可以实现python下最快的素数筛法。下面示范寻找第k个素数的python实现:
#---------------------Count Time------------------------
def Tim(X):
import time
def F(*a, **b):
t=time.time()
a=X(*a, **b)
print("[{0}s @{1}]".format(time.time()-t, X.__name__))
return a
return F
#---------------------Primest---------------------------
@Tim
def Primest(K):
N=K*24
r=bytearray([1])*(N//3);r[0]=0;j=2
for i in range(int(N**0.5)//3+1):
if r[i]:
I=3*i+1|1
r[((I*I)//3)::2*I]=bytearray([0])*((N//6-(I*I)//6-1)//I+1)
r[(I*I+4*I-2*I*(i&1))//3::2*I]=bytearray([0])*((N//6-(I*I+4*I-2*I*(i&1))//6-1)//I+1)
for i,p in enumerate(r):
if p:
j+=1
if j==K:
print("* The {0}st prime number is :{1}".format(K,i*3+1|1))
break
#-------------------------------------------------------
Primest(10001) #调用Primest(K)函数,返回第K个素数
用上bytearray和分片函数,就实现了python下最快的素数筛法,几乎接近位压缩。不可能再快了!
回复

在线用户

正浏览此版面之用户: 没有注册用户 和 0 访客