(發(fā)現(xiàn)好多博客對(duì)第三種進(jìn)階方法說(shuō)的不明白，至少我是沒(méi)完全看明白。后面結(jié)合自己的理解應(yīng)該算是弄懂了，供大家參考，歡迎糾正。)

方法一：最暴力，最簡(jiǎn)單，也最耗時(shí)O(n)

思想：由素?cái)?shù)的定義：一個(gè)數(shù)t，除了1和它本身，若沒(méi)有其他因數(shù)，那么就稱(chēng)其為素?cái)?shù)。因此循環(huán)i從2開(kāi)始到t-1，依次判斷t是否將i整除，若是則不為素?cái)?shù)。

代碼：

# 判斷是否為質(zhì)數(shù)
def is_zhishu(t):
    if t <= 1:
        # 1和0都不是質(zhì)數(shù)
        return False
    for i in range(2, t):
        if t % i == 0:
            # 整除就是余數(shù)為0 只要有一個(gè)被整除 就找到因數(shù) 就不是質(zhì)數(shù)
            return False
    return True

t = int(input())
print(is_zhishu(t))

方法二：

一個(gè)數(shù)t，其必然可以拆解為,則其整數(shù)因數(shù)必然一個(gè)不大于,一個(gè)不小于.因此可以只搜索小于等于的因數(shù)即可，將上述代碼小改一下即可。此時(shí)時(shí)間復(fù)雜度就只需要O().

代碼：

# 判斷是否為質(zhì)數(shù)
import math
def is_zhishu(t):
    if t <= 1:
        # 1和0都不是質(zhì)數(shù)
        return False
    sqrt_t = math.ceil(t**0.5)  # 這里用ceil的原因是要取整數(shù)才能輸入range
    for i in range(2, sqrt_t):
        if t % i == 0:
            # 整除就是余數(shù)為0 只要有一個(gè)被整除 就找到因數(shù) 就不是質(zhì)數(shù)
            return False
    return True

t = int(input())
print(is_zhishu(t))

方法三：

時(shí)復(fù)<=O().

方法三基于如下一個(gè)規(guī)律：

首先。對(duì)于任一個(gè)自然數(shù)t，只要t>=5, 則可以寫(xiě)成6x-1,6x,6x+1,6x+2,6x+3,6x+4,...(x>=1)中的任一個(gè)。其次，針對(duì)上面的這種表達(dá)，依次看其是否是質(zhì)數(shù)。

• 6x-1: 不能確定(因?yàn)橄?5=6*6-1不是質(zhì)數(shù)，但41=6*7-1是質(zhì)數(shù)，因此暫時(shí)不能確定)
• 6x: 因數(shù)可以是2,3,6，必定不是質(zhì)數(shù)
• 6x+1: 不能確定(因?yàn)橄?5=4*6+1不是質(zhì)數(shù)，但37=6*6+1是質(zhì)數(shù)，因此暫時(shí)不能確定)
• 6x+2: =2(3x+1)因數(shù)可以是2，必定不是質(zhì)數(shù)
• 6x+3: =3(2x+1)因數(shù)可以是3，必定不是質(zhì)數(shù)
• 6x+4: =2(3x+2)因數(shù)可以是2，必定不是質(zhì)數(shù)

因此，對(duì)于t>=5，只有t可以寫(xiě)成t=6x-1或者t=6x+1(x>=1)時(shí)才有可能是質(zhì)數(shù)。那么判斷t是否可以寫(xiě)成這兩種形式該如何體現(xiàn)在代碼上呢？

• 首先我們知道代碼中t%6 == 1,表示t = 6x+1(x>=0)的t都能識(shí)別出來(lái)，因此判斷t>=5時(shí)可以被寫(xiě)成這種形成t=6x+1(x>=1)的就直接用t%6 == 1來(lái)判斷即可，因?yàn)榭梢员蛔R(shí)別出來(lái)即可。
• 而t=6x-1(x>=1)，這個(gè)-1的要如何識(shí)別出來(lái)呢？這個(gè)直接體現(xiàn)是體現(xiàn)不了在余數(shù)上的，因此需要轉(zhuǎn)換一下，t=6x-1(x>=1)等價(jià)于t=6(x+1)-1(x>=0)=6x+5(x>=0). 類(lèi)似上一個(gè)所說(shuō)，t%6 == 5,表示t = 6x+5(x>=0)的t都能識(shí)別出來(lái).因此這時(shí)只需要用t%6 == 5來(lái)識(shí)別t=6x-1(x>=1)這種情況即可。

所以代碼中將可能是質(zhì)數(shù)的先提取出來(lái)。即當(dāng)t>=5時(shí)將不是質(zhì)數(shù)的先判斷為False。

前半部分：

if t <= 1 or t == 4:
    return False
elif t == 2 or t == 3:
    return True
    # 至此 先把t<5的情況全部討論完，再看t>=5有規(guī)律的情況
elif t%6 != 1 and t%6 != 5:
    # 這里采用！= 就是將可能為質(zhì)數(shù)的提取出來(lái)，！= 的就一定不是質(zhì)數(shù)
    return False

那么接下來(lái)就是如何判斷t=6x-1或者t=6x+1(x>=1)這兩種形式到底是不是質(zhì)數(shù)的問(wèn)題了。首先我們采用方法二的大方向，這兩種數(shù)如果不是質(zhì)數(shù)，那么其必定會(huì)有一個(gè)因數(shù)不大于根號(hào)t，這樣就找到了遍歷時(shí)的右邊界i = 根號(hào)t向上取整。那么i是從幾開(kāi)始，間隔又是幾遞增呢？直接搜會(huì)告訴你i從5開(kāi)始，間隔是6，這是為什么？很多博客中說(shuō)因?yàn)閠=6x-1或者t=6x+1(x>=1)，可是這個(gè)是t，又不是t的因數(shù)。那么為什么t的因數(shù)又只有6x-1或6x+1這兩種形式呢？請(qǐng)看我細(xì)細(xì)道來(lái)。

• 首先，t=6x-1或者t=6x+1(x>=1)這兩種形式的數(shù)的因數(shù)也只可能為6x-1或者6x+1(x>=1),因?yàn)槠渌麛?shù)的形式6x,6x+2,6x+3,6x+4(x>=0)(這里如果取6x則x>=1)要么一定有最小因數(shù)2要么一定有最小因數(shù)3，因此都不可能是t=6x-1或者t=6x+1(x>=1)的因數(shù)(這個(gè)前面分析過(guò)了，因?yàn)槠洳还茉趺床鸲疾鸩怀?和3).因此對(duì)于t=6x-1或者t=6x+1(x>=1)這兩種形式的數(shù)的因數(shù)也只可能為6x-1或者6x+1(x>=1)的形式[這里相當(dāng)于從5開(kāi)始了，是因?yàn)?不算因數(shù)，2和3剛已經(jīng)說(shuō)了不可能為t的因數(shù)了，4(因?yàn)榭梢圆鸪?)因此不可能是t的因數(shù)了]。所以現(xiàn)在就知道i從5開(kāi)始！且因?yàn)?x-1或者6x+1(x>=1)都有可能成為t的因數(shù)，因此每遍歷一次i就要有兩次判斷！(分別針對(duì)6x-1和6x+1的，i從5開(kāi)始即每次取i時(shí)就是在判斷6x-1(x>=1)，取i+2時(shí)就是在判斷6x+1(x>=1))，即t%i ==0 or t%(i+2) ==0,一旦有能被整除的就是False。現(xiàn)在i遞增是6就很容易理解了，第一輪x=1時(shí)6x-1=5;判斷完后第二輪x=2時(shí)6x-1 = 6(x-1)-1+6,因此每次遞增6就可以將6x-1(x>=1)剛好全部判斷完。
• 沒(méi)有然后了，已經(jīng)結(jié)束，看不懂慢慢讀多讀幾遍首先那一段就OK，不要著急。

方法三的完整代碼：

import math
def is_zhishu(t):
    # 先把小于5的所有情況討論完
    if t <= 1 or t == 4:
        return False
    elif t in (2,3):
        return True
    # 至此 t都是>=5的情況，這時(shí)就可以把t不是=6x-1,6x+1(x>=1)這兩種情況過(guò)濾掉
    elif t%6 != 1 and t%6 != 5:
        return False
    # 此時(shí)基于t>=5基礎(chǔ)上把有可能是質(zhì)數(shù)的t=6x-1or6x+1(x>=1)的兩種情況提取出來(lái)
    # 按照前面所說(shuō)遍歷i從5開(kāi)始，遞增6，至sqrt_t去尋找其因數(shù),每輪要識(shí)別i(對(duì)應(yīng)6x-1這種因數(shù))和(i+2)(對(duì)應(yīng)6x+1這種因數(shù))
    sqrt_t = math.ceil(t**0.5)
    for i in range(5, sqrt_t, 6):
        if t % i == 0 or t %(i+2) == 0:
            return False
    return True

t = int(input())
print(is_zhishu(t))

總結(jié) 

到此這篇關(guān)于Python判斷一個(gè)數(shù)是否為質(zhì)數(shù)的3種方法的文章就介紹到這了,更多相關(guān)Python判斷一個(gè)數(shù)為質(zhì)數(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論