素?cái)?shù)算法
看到廖雪峰網(wǎng)站上用python的實(shí)現(xiàn), 看起來(lái)很簡(jiǎn)單, 但是最終還是自己實(shí)現(xiàn)一遍比較好, ==代碼點(diǎn)我跳轉(zhuǎn).==
- 素?cái)?shù)算法 (埃拉托色尼篩選法)
原理很簡(jiǎn)單, 在數(shù)學(xué)界1既不是質(zhì)數(shù)也不是合數(shù), 所以不用管1, 從2開(kāi)始
輸出最小的質(zhì)數(shù)`2`, 然后將`2`的倍數(shù)都刪除
輸出剩下的第一個(gè)數(shù)為`3`, 然后將`3`的倍數(shù)都刪除
輸出剩下的第一個(gè)數(shù)為`5`, 然后將`5`的倍數(shù)都刪除
輸出剩下的第一個(gè)數(shù)為`7`, 然后將`7`的倍數(shù)都刪除
...
這樣不斷循環(huán)下去, 直到所有的數(shù)都被刪除或者輸出, 輸出的數(shù)即為質(zhì)數(shù).
- 實(shí)現(xiàn)
def _ori_iter():
n = 1
while True:
n += 2
yield n
這里先定義一個(gè)ori_iter方法, 返回的是一個(gè)生成器(從3開(kāi)始的奇數(shù), 如 3, 5, 7...)
def _not_divisible(n):
return lambda x: x % n > 0
這里定義了一個(gè)_not_divisible方法, 這可以理解成一種規(guī)則, x能整除n返回false, 不能整除則返回true, 后面filter中有用到
def prime():
it = _ori_iter()
while True:
n = next(it)
yield n
# it = filter(lambda x: x % n > 0, it)
it = filter(_not_divisible(n), it)
這里定義的prime返回的則是全體素?cái)?shù). 第一行的it = _ori_iter(), 這時(shí)it是一個(gè)會(huì)返回從3開(kāi)始的所有奇數(shù)(也就是不能被2整除)的生成器==(3, 5, 7, 9, 11...)==, while True表示將會(huì)無(wú)限循環(huán)下去,直到天荒地老, 下面是循環(huán)過(guò)程
- 取出的第一個(gè)
n是it的第一個(gè)元素3,yield n將3作為prime生成器的第一個(gè)元素. 之后經(jīng)過(guò)it = filter(_not_divisible(n), it), 這里的it經(jīng)過(guò)篩選, 將3的倍數(shù)全部丟棄==(3, 5, 7,9, 11...)== - 取出被篩選過(guò)的
it的第二個(gè)元素, 也就是5, 作為prime生成器的第二個(gè)元素. 之后在經(jīng)過(guò)it = filter(_not_divisible(n), it)篩選, 將5的倍數(shù)全部丟棄(3, 5, 7, 11, 13,15...) - 取出被篩選過(guò)的
it的第三個(gè)元素, 也就是7, 作為prime生成器的第三個(gè)元素. 之后在經(jīng)過(guò)it = filter(_not_divisible(n), it)篩選, 將7的倍數(shù)全部丟棄(3, 5, 7, 11, 13...21...) - ...
這是一個(gè)無(wú)限循環(huán), 所以prime返回的是一個(gè)的生成器, 里面包含無(wú)窮多個(gè)質(zhì)數(shù)
- 總結(jié)
算法很容易理解, 實(shí)現(xiàn)起來(lái)也并不難, 下面是在實(shí)現(xiàn)的過(guò)程中遇到的一個(gè)問(wèn)題
def _not_divisible(n):
return lambda x: x % n > 0
def prime():
it = _ori_iter()
while True:
n = next(it)
yield n
# it = filter(lambda x: x % n > 0, it)
it = filter(_not_divisible(n), it)
最后兩句分為注釋部分it = filter(lambda x: x % n > 0, it)和未注釋部分it = filter(_not_divisible(n), it)咋一看并沒(méi)有什么區(qū)別, 但是輸出的結(jié)果卻大有不同, 這就有意思了, 思前想后, 請(qǐng)教同事, 最后總算是有點(diǎn)理解, 這里大致描述一下為什么會(huì)出現(xiàn)輸出不同的情況...
生成器(Iterator)是一種惰性計(jì)算的序列(他很懶, 你催他一下, 他才會(huì)給你下一個(gè)數(shù)據(jù)- -), 只有當(dāng)你使用next取值時(shí), 才會(huì)去執(zhí)行, 然后返回給你正確的值
- 這里如果使用未注釋部分,
it = filter(lambda x: x % n > 0, it)這里的n值確實(shí)是上一句正確返回的n值, 但是由于filter也是惰性的,filter只會(huì)去執(zhí)行一次篩選, 然后到下次循環(huán)時(shí),n的值就變了成下次返回的n, 這樣每次filter都只會(huì)篩選一次, 真正需要篩選出去的值并沒(méi)有被篩選, 最后的執(zhí)行結(jié)果顯然不會(huì)正確了... - 然而使用未注釋部分代碼,
n的值是通過(guò)_not_divisible函數(shù)的參數(shù)傳進(jìn)去的, 不會(huì)去改變, 傳進(jìn)去第一個(gè)3, 他就會(huì)一直篩選下去, 然后傳進(jìn)第二個(gè)5的時(shí)候, 同理也會(huì)篩選下去, 所以可以得出正確的質(zhì)數(shù)序列
歸根結(jié)底, 這里應(yīng)該是filter和lambda內(nèi)部處理的問(wèn)題, 可能研究一下源碼會(huì)更加明了, 這里就先不倒騰了/哭笑...
