目的:使用埃氏篩法構造素數(shù)
計算素數(shù)的一個方法是埃氏篩法,它的算法理解起來非常簡單:
首先,列出從2開始的所有自然數(shù),構造一個序列:
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, …
取序列的第一個數(shù)2,它一定是素數(shù),然后用2把序列的2的倍數(shù)篩掉:
3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, …
取新序列的第一個數(shù)3,它一定是素數(shù),然后用3把序列的3的倍數(shù)篩掉:
5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, …
取新序列的第一個數(shù)5,然后用5把序列的5的倍數(shù)篩掉:
7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, …
不斷篩下去,就可以得到所有的素數(shù)。
代碼實現(xiàn)
#_*_coding:utf_8_*_
def iters():#先構造一個從3開始的奇數(shù)序列。這是一個生成器,并且是一個無限序列
n=1
while 1:
n=n+2
yield n
def isinit(n):#篩選函數(shù)
return lambda x:x%n>0
def prime():
yield 2
it=iters()# 初始序列
while 1:
n=next(it)# 返回序列的第一個數(shù)
yield n
it=filter(isinit(n),it)# 構造新序列
for n in prime():
if(n<10):
print(n)
else:
break
問題
在python3中能夠直接運行,完美出結果,但是在python2中只出現(xiàn)第一個結果,后面就卡死了。原因是什么呢?搜了好多資料沒有這個的說明,在大神那里得到了答案。
filter() 函數(shù):python2 會把你的 it 遍歷完再直接返回一個 list。python3 不需要遍歷完,它返回一個iterable
解決方法:
自己實現(xiàn)filter方法,重寫里面的邏輯,如下:
def filter(func, it):
while 1:
v = next(it)
if func(v):
yield v
至此,上面代碼在python2中也可以完美運行了。
更多文章、技術交流、商務合作、聯(lián)系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯(lián)系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
