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

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

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

代碼：

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

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

方法二：

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

代碼：

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

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

方法三：

時復<=O().

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

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

• 6x-1: 不能確定(因為像35=6*6-1不是質數，但41=6*7-1是質數，因此暫時不能確定)
• 6x: 因數可以是2,3,6，必定不是質數
• 6x+1: 不能確定(因為像25=4*6+1不是質數，但37=6*6+1是質數，因此暫時不能確定)
• 6x+2: =2(3x+1)因數可以是2，必定不是質數
• 6x+3: =3(2x+1)因數可以是3，必定不是質數
• 6x+4: =2(3x+2)因數可以是2，必定不是質數

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

• 首先我們知道代碼中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的要如何識別出來呢？這個直接體現是體現不了在余數上的，因此需要轉換一下，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)這種情況即可。

所以代碼中將可能是質數的先提取出來。即當t>=5時將不是質數的先判斷為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:
    # 這里采用！= 就是將可能為質數的提取出來，！= 的就一定不是質數
    return False

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

• 首先，t=6x-1或者t=6x+1(x>=1)這兩種形式的數的因數也只可能為6x-1或者6x+1(x>=1),因為其他數的形式6x,6x+2,6x+3,6x+4(x>=0)(這里如果取6x則x>=1)要么一定有最小因數2要么一定有最小因數3，因此都不可能是t=6x-1或者t=6x+1(x>=1)的因數(這個前面分析過了，因為其不管怎么拆都拆不出2和3).因此對于t=6x-1或者t=6x+1(x>=1)這兩種形式的數的因數也只可能為6x-1或者6x+1(x>=1)的形式[這里相當于從5開始了，是因為1不算因數，2和3剛已經說了不可能為t的因數了，4(因為可以拆成2)因此不可能是t的因數了]。所以現在就知道i從5開始！且因為6x-1或者6x+1(x>=1)都有可能成為t的因數，因此每遍歷一次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在i遞增是6就很容易理解了，第一輪x=1時6x-1=5;判斷完后第二輪x=2時6x-1 = 6(x-1)-1+6,因此每次遞增6就可以將6x-1(x>=1)剛好全部判斷完。
• 沒有然后了，已經結束，看不懂慢慢讀多讀幾遍首先那一段就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基礎上把有可能是質數的t=6x-1or6x+1(x>=1)的兩種情況提取出來
    # 按照前面所說遍歷i從5開始，遞增6，至sqrt_t去尋找其因數,每輪要識別i(對應6x-1這種因數)和(i+2)(對應6x+1這種因數)
    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))

總結 

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

最新評論