使用Python判斷素數

介紹

素數是指除了1和本身以外，不能被其他正整數整除的數。判斷一個數是否為素數，在計算機編程中非常常見。Python作為一門高級編程語言，也可以用來進行素數的判斷。

判斷素數的方法

試除法

試除法是最簡單的一種方法，即判斷一個數 n 是否為素數，只需在 2 到 n-1 的範圍內判斷 n 是否被整除。

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

質數倍數法

質數倍數法是一種非常有效的方法，可以處理較大的素數。它的基本思想是從 2 開始，不斷將它的倍數標記為合數，直到所需要的素數都被找到，這種方法可以大大減少試除數的個數。

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

小標題

生成素數序列

可以通過生成素數序列的方式，找到所有小於等於給定值的素數。下面是利用試除法生成素數序列的代碼：

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

這段代碼利用一個布爾型列表 is_prime 記錄每個數是否為素數。首先將 is_prime 中的每個元素置為 True，然後從 2 開始，在 range(2, int(n ** 0.5) + 1) 中循環，如果 is_prime[i] 為 True，那麼將 i * 2、i * 3、i * 4 …… 等數全部標記為 False。

多重判斷素數

為了判斷一個大整數是否為素數，可以使用多重判斷法，例如同餘檢驗法、費馬小定理等。其中，費馬小定理的判斷方式比較簡單，可以用下面的代碼實現：

def is_prime(n):
    if n <= 1:
        return False
    elif n <= 3:
        return True
    elif n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

總結

判斷素數是計算機編程中的基本技能之一，Python提供了多種計算方式，包括試除法、質數倍數法、費馬小定理等。如果要處理大的素數，可以使用更加高效的多重判斷素數的方法。無論使用哪種方法，都需要注意處理好邊界情況，以保證程序的正確性。