使用 Python 判斷素數

一、介紹

素數，也稱質數，指在大於1的自然數中，除了1和本身以外，無法被其他自然數整除的數。素數的判斷是數學中的基礎問題之一，在編程中也常常用到。Python 是一種高級編程語言，具有簡潔的語言結構和易於理解的語法，極大地方便了素數的計算與判斷。

二、Python 判斷素數的方法

1. 最簡單的方法

最簡單的方法是判斷一個數是否為素數，只需要枚舉從2到該數的平方根的所有數，判斷是否有因子。如果有因子，那麼該數不是素數。如果沒有因子，那麼該數是素數。

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

以上代碼中的函數 is_prime(n) 接收一個整數參數 n，並返回一個布爾值，表示該數是否為素數。首先，如果 n 小於等於 1，那麼該數不是素數，因為素數必須大於 1。接着，通過 for 循環枚舉從 2 到 int(n ** 0.5) + 1 的所有數，並檢查是否能整除 n，如果能整除，那麼該數不是素數。如果所有枚舉的數都不能整除 n，那麼該數是素數。最後，函數返回一個布爾值。

2. 利用質數的性質

質數具有以下性質：

• 質數只能被 1 和本身整除；
• 質數與其他數的乘積，只能是它本身與 1 相乘。

因此，只需要枚舉從 2 到該數的一半中的所有質數，判斷是否有因子。如果有因子，那麼該數不是素數。如果沒有因子，那麼該數是素數。

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

以上代碼中的函數 is_prime(n) 和 最簡單的方法 中的函數 is_prime(n) 相比，增加了三個判斷。首先，如果 n 小於等於 1，那麼該數不是素數，因為素數必須大於 1。然後，判斷如果 n 等於 2，那麼該數是素數，因為 2 是最小的質數。接着，判斷如果 n 能被 2 整除，那麼該數不是素數。因為如果 n 是大於 2 的偶數，那麼它必然不是質數。最後，通過 for 循環枚舉從 3 到 int(n ** 0.5) + 1 的所有奇數（因為偶數已經判斷過了），並檢查是否能整除 n，如果能整除，那麼該數不是素數。如果所有枚舉的數都不能整除 n，那麼該數是素數。最後，函數返回一個布爾值。

3. Sieve of Eratosthenes 算法

Sieve of Eratosthenes 是一種求解質數的算法，它的基本思想是從小到大枚舉每個質數，將它的所有倍數標記成合數，重複這個過程，直到找出所有的質數。下面是用 Python 實現 Sieve of Eratosthenes 算法的代碼：

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

以上代碼中的函數 sieve(n) 接收一個正整數參數 n，並返回一個列表，包含 0 到 n 中的所有素數。

三、總結

Python 是一種高級編程語言，具有簡潔的語言結構和易於理解的語法，極大地方便了素數的計算與判斷。本文介紹了三種判斷素數的方法：最簡單的方法，利用質數的性質，以及 Sieve of Eratosthenes 算法。當然，這三個方法各有優劣，選擇哪種方法取決於場景和需求。希望本文能夠對讀者在 Python 中判斷素數方面提供幫助。