Python判斷質數方法用法介紹

本文將介紹如何用Python判斷一個數是否為質數。其中，我們將從多個方面進行闡述，包括質數的定義、判斷方法、演算法優化等內容，希望對Python初學者或對質數感興趣的讀者有所幫助。

一、什麼是質數

質數也稱素數，是指在大於1的正整數中，只能被1和該數本身整除的數。比如2、3、5、7、11、13等都是質數，而4、6、8、9、10等則不是質數。

之所以叫質數，是因為質數本身不能再拆分成不同的乘積形式，只有1和該數本身兩個因數。這種被分解為質數乘積表示的形式，稱為質因數分解。

質數在密碼學領域有廣泛應用，因為大質數的因數分解是計算機科學中的困難問題之一。

二、判斷質數的方法

方法一：試除法

試除法是判斷質數最簡單的方法，即判斷一個數n能否被2到n-1中的任意一個數整除。如果都不能整除，則n為質數。這種方法容易實現，但計算量大，效率較低。

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

上述代碼中，從2到n-1依次用n去除，如果有任何一個數能夠整除，則返回False，表示n不是質數。否則返回True，表示n是質數。

方法二：優化試除法

試除法的計算量較大，可以進行優化。通過觀察發現，如果一個數n不能被2至$\sqrt{n}$間的整數整除，那麼，它也肯定不能被$\sqrt{n}$到n-1間的整數整除。因此，在試除法中，只需要試除至$\sqrt{n}$即可。

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

上述代碼中，將n開方後找到整數位，並從2到整數位進行試除。這種演算法優化之後，計算量相對減少，但仍存在效率問題。

方法三：埃氏篩法

埃氏篩法用於求解給定範圍內的所有質數。具體實現方法是：先用2到n-1中的每一個數去除2，標記被整除的數，然後再用下一個未被標記的數3去除它未被標記的倍數，依次進行下去，直到最後，剩下的未被標記的數就是質數。

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0], is_prime[1] = False, False
    for i in range(2, int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i*i, n+1, i):
                is_prime[j] = False
    return [i for i, val in enumerate(is_prime) if val]

print(primes(100))

上述代碼中，使用一個列表is_prime記錄每個數是否是質數，初始都為True。從2開始遍歷列表，如果這個數是質數，則將它的倍數都標記為False。最後返回is_prime中為True的數，即為質數。

三、演算法優化

對於計算質數問題，演算法優化是個重要的議題。下面介紹兩種優化方式。

方式一：判斷奇數

一個數如果是偶數且不是2，則它肯定不是質數。因此，如果一開始判斷出一個數是偶數，則立刻返回False，避免後面的不必要計算。

def is_prime(n):
    if n < 2 or (n != 2 and n % 2 == 0):
        return False
    for i in range(3, int(n**0.5)+1, 2):
        if n % i == 0:
            return False
    return True

上述代碼中，在判斷前先特殊處理2和小於2的數，然後跳過所有的偶數試除。

方式二：Miller-Rabin演算法

Miller-Rabin演算法是一種分治演算法，用於判斷一個數是否是質數。由於Miller-Rabin演算法具有高效性和準確性，因此它被廣泛應用於RSA等密碼學演算法中。

Miller-Rabin演算法基於一個重要定理：如果n是一個質數，那麼對於任意整數a，有$a^{n-1}\equiv1 \pmod n$。該定理稱為費馬小定理(Fermat’s little theorem)。基於該定理，可以發展出Miller-Rabin演算法的偽代碼如下：

1. 將n-1分解成$2^s \cdot d$的形式
2. 針對每一個a，重複k次：
   a. 生成隨機數a，2<=a<=n-2；
   b. 計算$x_0 = a^d \pmod n$
   c. 對於r = 0至s-1，計算$x_r$ = $x_{r-1}^2 \pmod n$;
      如果$x_r = 1$且$r!=(s-1)$，則返回False
      如果$x_s != 1$，則返回False
      如果$x_s = 1$，則返回True

上述演算法的關鍵在於計算$a^d \pmod n$和$x_{r-1}^2 \pmod n$的過程，使用了模冪運算，可參考Python內置函數pow的實現方式。Miller-Rabin演算法的準確性與其迭代次數有關，可以設計固定的迭代次數得到較高的正確性，但無法證明其完全正確。

import random

def is_prime(n, k=5):
    if n < 2: 
        return False
    if n == 2 or n == 3: 
        return True
    if n % 2 == 0: 
        return False
    s, d = 0, n - 1
    while d % 2 == 0:
        s += 1
        d //= 2
    for i in range(k):
        a = random.randint(2, n - 1)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for r in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

print(is_prime(23))

上述代碼中，使用了Python內置函數pow進行模冪運算，通過計算多組隨機數，判斷是否為質數。可以自定義迭代次數k來調整準確性和效率。

四、總結

本文介紹了Python判斷質數的方法，包括試除法、優化試除法、埃氏篩法和Miller-Rabin演算法。其中，優化試除法和埃氏篩法更高效、更可靠。在實際使用中，可根據具體需求選擇合適的演算法並根據實際情況進行代碼優化。同時，也可以通過本文的介紹來深入理解質數的性質和計算方法。