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

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

思想：由素數(shù)的定義：一個數(shù)t，除了1和它本身，若沒有其他因數(shù)，那么就稱其為素數(shù)。因此循環(huán)i從2開始到t-1，依次判斷t是否將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 只要有一個被整除 就找到因數(shù) 就不是質(zhì)數(shù)
            return False
    return True

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

方法二：

一個數(shù)t，其必然可以拆解為,則其整數(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 只要有一個被整除 就找到因數(shù) 就不是質(zhì)數(shù)
            return False
    return True

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

方法三：

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

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

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

• 6x-1: 不能確定(因為像35=6*6-1不是質(zhì)數(shù)，但41=6*7-1是質(zhì)數(shù)，因此暫時不能確定)
• 6x: 因數(shù)可以是2,3,6，必定不是質(zhì)數(shù)
• 6x+1: 不能確定(因為像25=4*6+1不是質(zhì)數(shù)，但37=6*6+1是質(zhì)數(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ù)

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

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

所以代碼中將可能是質(zhì)數(shù)的先提取出來。即當(dāng)t>=5時將不是質(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ù)的提取出來，！= 的就一定不是質(zhì)數(shù)
    return False

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

• 首先，t=6x-1或者t=6x+1(x>=1)這兩種形式的數(shù)的因數(shù)也只可能為6x-1或者6x+1(x>=1),因為其他數(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ù)(這個前面分析過了，因為其不管怎么拆都拆不出2和3).因此對于t=6x-1或者t=6x+1(x>=1)這兩種形式的數(shù)的因數(shù)也只可能為6x-1或者6x+1(x>=1)的形式[這里相當(dāng)于從5開始了，是因為1不算因數(shù)，2和3剛已經(jīng)說了不可能為t的因數(shù)了，4(因為可以拆成2)因此不可能是t的因數(shù)了]。所以現(xiàn)在就知道i從5開始！且因為6x-1或者6x+1(x>=1)都有可能成為t的因數(shù)，因此每遍歷一次i就要有兩次判斷！(分別針對6x-1和6x+1的，i從5開始即每次取i時就是在判斷6x-1(x>=1)，取i+2時就是在判斷6x+1(x>=1))，即t%i ==0 or t%(i+2) ==0,一旦有能被整除的就是False?，F(xiàn)在i遞增是6就很容易理解了，第一輪x=1時6x-1=5;判斷完后第二輪x=2時6x-1 = 6(x-1)-1+6,因此每次遞增6就可以將6x-1(x>=1)剛好全部判斷完。
• 沒有然后了，已經(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的情況，這時就可以把t不是=6x-1,6x+1(x>=1)這兩種情況過濾掉
    elif t%6 != 1 and t%6 != 5:
        return False
    # 此時基于t>=5基礎(chǔ)上把有可能是質(zhì)數(shù)的t=6x-1or6x+1(x>=1)的兩種情況提取出來
    # 按照前面所說遍歷i從5開始，遞增6，至sqrt_t去尋找其因數(shù),每輪要識別i(對應(yīng)6x-1這種因數(shù))和(i+2)(對應(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判斷一個數(shù)是否為質(zhì)數(shù)的3種方法的文章就介紹到這了,更多相關(guān)Python判斷一個數(shù)為質(zhì)數(shù)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論