python寻找第k个素数

Life is short, you need Python - Bruce Eckel
Package Index, Python 3.5.3 documentation
happy886rr
渐入佳境
渐入佳境
帖子: 45
注册时间: 2016年09月27日 16:11
拥有现金: 锁定
储蓄: 锁定
Has thanked: 14 times
Been thanked: 14 times
联系:

python寻找第k个素数

帖子 #1 happy886rr » 2016年09月28日 19:45

在python中分片的扩展形式:str[I:J:K]意思是从I到J-1,每隔K个元素索引一次,如果K为负数,就是按从右往左索引。用这个分片函数,就可以实现python下最快的素数筛法。下面示范寻找第k个素数的python实现:
Code: [全选] [展开/收缩] [Download] (Untitled.py)
  1. #---------------------Count Time------------------------
  2. def Tim(X):
  3.     import time
  4.     def F(*a, **b):
  5.         t=time.time()
  6.         a=X(*a, **b)
  7.         print("[{0}s @{1}]".format(time.time()-t, X.__name__))
  8.         return a
  9.     return F
  10. #---------------------Primest---------------------------
  11. @Tim
  12. def Primest(K):
  13.     N=K*24
  14.     r=bytearray([1])*(N//3);r[0]=0;j=2
  15.     for i in range(int(N**0.5)//3+1):
  16.         if r[i]:
  17.             I=3*i+1|1
  18.             r[((I*I)//3)::2*I]=bytearray([0])*((N//6-(I*I)//6-1)//I+1)
  19.             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)
  20.     for i,p in enumerate(r):
  21.         if p:
  22.             j+=1
  23.             if j==K:
  24.                 print("* The {0}st prime number is :{1}".format(K,i*3+1|1))
  25.                 break
  26. #-------------------------------------------------------
  27. Primest(10001)      #调用Primest(K)函数,返回第K个素数

用上bytearray和分片函数,就实现了python下最快的素数筛法,几乎接近位压缩。不可能再快了!

回到 “Python”

在线用户

用户浏览此论坛: Baidu [Spider] 和 1 访客