素?cái)?shù)判斷代碼實(shí)現(xiàn)及其優(yōu)化
說(shuō)在前面
素?cái)?shù)判斷是經(jīng)典數(shù)論問(wèn)題，也是算法教學(xué)中的經(jīng)典案例，利用素?cái)?shù)定義判斷正整數(shù)n是否為素?cái)?shù)，是解決復(fù)雜素?cái)?shù)問(wèn)題的基礎(chǔ)，該問(wèn)題涉及循環(huán)結(jié)構(gòu)和枚舉算法，其代碼實(shí)現(xiàn)形式多樣，可作為入門(mén)級(jí)算法學(xué)習(xí)的經(jīng)典例題，值得深入研究。
自定義函數(shù)is_prime(n)的功能是判斷正整數(shù)n是否為素?cái)?shù)，若為素?cái)?shù)返回True，否則返回False。請(qǐng)將缺失的代碼補(bǔ)充完整。
def is_prime(n):
flag = True
for i in range(2, n):
if 填空1:
flag = False
填空2
題目解析：
根據(jù)素?cái)?shù)的定義可知，素?cái)?shù)不能被1和它本身外的自然數(shù)整除，若n能被i整除，說(shuō)明n不是素?cái)?shù)。故第1空答案為n % i == 0。
變量flag用來(lái)標(biāo)記n是否為素?cái)?shù)，先假設(shè)n為素?cái)?shù)，為flag取初值True。若n不是素?cái)?shù)，則設(shè)置flag=False。函數(shù)返回flag的值表示判斷結(jié)果，故第2空答案為return flag。
拓展思考1：
教師：函數(shù)is_prime()使用for循環(huán)來(lái)遍歷n所有可能的因數(shù)，以判斷其是否為素?cái)?shù)。我們知道for語(yǔ)句和while語(yǔ)句都可以實(shí)現(xiàn)循環(huán)結(jié)構(gòu)功能，那么在本例中又該怎么做呢？
學(xué)生甲：循環(huán)結(jié)構(gòu)必須包含3個(gè)環(huán)節(jié)：為循環(huán)變量i設(shè)置初值、判斷循環(huán)結(jié)束條件和更新循環(huán)變量的值。for循環(huán)語(yǔ)句比較簡(jiǎn)明，它把這3個(gè)環(huán)節(jié)都濃縮在一條語(yǔ)句中了，而while循環(huán)需要使用3條語(yǔ)句才能實(shí)現(xiàn)這3個(gè)功能。參考代碼如下：
def is_prime2(n):
flag = True
i = 2
while i < n:
if n % i == 0:
flag = False
i += 1
return flag
拓展思考2：
flag = True
i = 2
while i < n:
if n % i == 0:
flag = False
break
i += 1
return flag
教師：非常好！充分利用了break語(yǔ)句的特性，直接跳出循環(huán)，減少循環(huán)次數(shù)。還有別的方法嗎？
改進(jìn)方案二：
拓展思考3：
教師：設(shè)置標(biāo)記變量flag來(lái)表示某種狀態(tài)是常用的編程技巧，在上述程序中變量flag用來(lái)標(biāo)記n是否為素?cái)?shù)，最后返回flag的值。那么，變量flag是否是必需的呢？如果不定義flag，能否實(shí)現(xiàn)函數(shù)功能呢？
def is_prime7(n):
i = 2
while i < n:
if n % i == 0:
break
i += 1
填空1
學(xué)生?。焊鶕?jù)代碼可知，若n為素?cái)?shù)，則程序沒(méi)有機(jī)會(huì)執(zhí)行break語(yǔ)句，while循環(huán)結(jié)束后，有i==n；否則執(zhí)行break語(yǔ)句，中途跳出while循環(huán)，循環(huán)結(jié)束后仍然滿足i<n。故填空1的答案為return i == n。
教師：非常棒！此處雖然沒(méi)有設(shè)置標(biāo)記變量，但是利用了while循環(huán)的特性，根據(jù)循環(huán)結(jié)束后循環(huán)條件是否依然成立來(lái)判斷程序是否執(zhí)行了break語(yǔ)句，構(gòu)思非常巧妙。
改進(jìn)方案三：
學(xué)生甲：老師，我還有更好的方法！
教師：是嗎？說(shuō)來(lái)聽(tīng)聽(tīng)。
學(xué)生甲：函數(shù)is_prime7()雖然構(gòu)思巧妙，但是不過(guò)直白，需要轉(zhuǎn)一道彎才能理解?？紤]到這是一個(gè)自定義函數(shù)，我們可以在找到n的第一個(gè)因數(shù)后直接返回False；只有當(dāng)n不存在因數(shù)時(shí)，才返回True。這樣代碼更簡(jiǎn)明，參考代碼如下：
def is_prime8(n):
for i in range(2, int(n**0.5)+1):
if n % i == 0:
return False
return True
教師：太棒了！既簡(jiǎn)單明了，又清晰易懂！簡(jiǎn)直是返璞歸真??！
需要本文word文檔、源代碼和課后練習(xí)答案的，可以加入“Python算法之旅”知識(shí)星球參與討論和下載文件，“Python算法之旅”知識(shí)星球匯集了數(shù)量眾多的同好，更多有趣的話題在這里討論，更多有用的資料在這里分享。
我們專(zhuān)注Python算法，感興趣就一起來(lái)！
相關(guān)優(yōu)秀文章：