Python判斷素數(shù)的3種方法及for-else語句的用法介紹

更新時間：2024年05月03日 11:57:09 作者：Zaly.

素數(shù)又叫質數(shù),指的是＞1的整數(shù)中,只能被1和這個數(shù)本身整除的數(shù),這篇文章主要給大家介紹了關于Python判斷素數(shù)的3種方法及for-else語句的用法介紹的相關資料,文中通過代碼介紹的非常詳細,需要的朋友可以參考下

題目

輸入一個數(shù)，如果是素數(shù)就輸出"Yes"，否則輸出"No"

方法一：暴力枚舉法

def is_prime(x):
    if x==1:
        return False;
    for i in range(2,x):
        if x%i==0:
            return False
    return True
n=int(input())
if is_prime(n):
    print("Yes")
else:
    print("No")

自定義函數(shù)is_prime()，首先排除1，然后再對該數(shù)之前的數(shù)進行枚舉，當遇到能被當前的數(shù)整除時返回False，若沒有數(shù)能將其整除意味著這個數(shù)是素數(shù)，返回True。然后對返回的結果進行判斷從而輸出"Yes"或"No"

當然，我們可以省去最后if-else的判斷，直接在函數(shù)is_prime()里來輸出"Yes"或"No"

def is_prime(x):
    if x==1:
        print("No")
        return
    for i in range(2,x):
        if x%i==0:
            print("No")
            break
    else:
        print("Yes")
n=int(input())
is_prime(n)

for-else語句

在上面的代碼中，我采用了for-else語句，這是一個比較特殊的語句。當for循環(huán)正常結束時，else也會執(zhí)行，而當for循環(huán)未正常結束，例如使用break提前退出時，則不會執(zhí)行。使用這個語句往往可以減少代碼量，避免使用flag。

方法二：內置函數(shù)

import sympy
n = int(input())
if sympy.isprime(n):
    print("Yes")
else:
    print("No")

使用python自帶的sympy庫中的isprime()函數(shù)僅需一行就能判斷素數(shù)

方法三：優(yōu)化了時間復雜度

import math
def is_prime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    for i in range(5, int(math.sqrt(n)) + 1, 6):
        if n % i == 0 or n % (i + 2) == 0:
            return False
    return True

優(yōu)化后的代碼利用了以下觀察：

1.所有的素數(shù)都是6的倍數(shù)加減1（除了2和3）。

2.如果n可以整除2或3，它肯定不是素數(shù)。

3.如果n不是2或3的倍數(shù)，并且不能整除6的倍數(shù)加減1的數(shù)，那么它也不是素數(shù)。所以可以只在6的倍數(shù)加減1的數(shù)中進行枚舉，跳過其他數(shù)字。這樣可以減少循環(huán)的次數(shù)，提高效率。

附：打印素數(shù)

方法一：

1、打印指定范圍內的素數(shù)

def sushu3(c):
    import math
    m = 2
    List = []
    while m < c:
        j = 2
        # 只要從2判斷到根號m，若m不能被其中的任何一個數(shù)整除，則m為素數(shù)
        while j <= math.sqrt(m):
            if m % j == 0:
                break
            j = j + 1
        if (j > math.sqrt(m)):
            List.append(m)
        m = m + 1
    print(f"{c}以內的素數(shù)：{List}")
    
 # 調用方法sushu3方法，打印100以內的素數(shù)
if __name__ == '__main__':
    sushu3(100)

方法二：

2、打印指定區(qū)間內的素數(shù)

def sushu4():
    Min = int(input("請輸入起始值："))
    Max = int(input("請輸入終止值："))
    List = []
    # 循環(huán)遍歷指定區(qū)間內的數(shù)
    for i in range(Min, Max + 1):
        if i > 1:
           # 除了1和本身以外的數(shù)，如果能被除則break退出
            for j in range(2, i):
                if (i % j) == 0:
                    break
            # 若不能被1和本身的數(shù)除則追加到List列表
            else:
                List.append(i)
    print(f"{Min}~{Max}區(qū)間內的素數(shù)有：{List}")