首先究孕，列出從2開(kāi)始的所有自然數(shù)溃槐，構(gòu)造一個(gè)序列：
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...
取序列的第一個(gè)數(shù)2厦幅，它一定是素?cái)?shù)哮幢，然后用2把序列的2的倍數(shù)篩掉：
3,4, 5,6, 7,8, 9,10, 11,12, 13,14, 15,16, 17,18, 19,20, ...
取新序列的第一個(gè)數(shù)3芯勘，它一定是素?cái)?shù)缰犁，然后用3把序列的3的倍數(shù)篩掉：
5,6, 7,8,9,10, 11,12, 13,14,15,16, 17,18, 19,20, ...
取新序列的第一個(gè)數(shù)5，然后用5把序列的5的倍數(shù)篩掉：
7,8,9,10, 11,12, 13,14,15,16, 17,18, 19,20, ...
不斷篩下去捡偏，就可以得到所有的素?cái)?shù)唤冈。
用Python來(lái)實(shí)現(xiàn)這個(gè)算法，可以先構(gòu)造一個(gè)從3開(kāi)始的奇數(shù)序列：
def_odd_iter():
? ? ? ? ? n =1
? ? ? ? ? while True:? ? ? ??
? ? ? ? ? ? ? ? ?n = n +2
? ? ? ? ? ? ? ? ?yield ?n
注意這是一個(gè)生成器霹琼，并且是一個(gè)無(wú)限序列务傲。
然后定義一個(gè)篩選函數(shù)：
def_not_divisible(n):
? ? ?return ? ?lambda x: x % n >0
最后，定義一個(gè)生成器枣申，不斷返回下一個(gè)素?cái)?shù)：
defprimes():
? ? yield 2
? ? ?it = _odd_iter()# 初始序列
? ? ?while True:? ? ? ??
? ? ? ? ? ? n = next(it)# 返回序列的第一個(gè)數(shù)yieldn? ? ? ? it = filter(_not_divisible(n), it)#?
構(gòu)造新序列
這個(gè)生成器先返回第一個(gè)素?cái)?shù)2，然后看杭，利用filter()不斷產(chǎn)生篩選后的新的序列忠藤。
由于primes()也是一個(gè)無(wú)限序列，所以調(diào)用時(shí)需要設(shè)置一個(gè)退出循環(huán)的條件：
# 打印1000以內(nèi)的素?cái)?shù):
for n in primes():
? ? if ?n <1000:? ? ? ??
? ? ? ? ?print(n)
? ? else:
? ? ? ? ? break
注意到Iterator是惰性計(jì)算的序列楼雹，所以我們可以用Python表示“全體自然數(shù)”模孩，“全體素?cái)?shù)”這樣的序列尖阔，而代碼非常簡(jiǎn)潔。
