1. 前言
由於 Python 擁有簡潔易懂的語法，因此非常受程式設計初學者歡迎。其中，「質數判斷」這個主題，是學習演算法基礎的絕佳題材。本文將從質數的基本概念開始，深入解說各種高效的判斷演算法，並提供 Python 的實作範例。為了讓初學者也能理解，我們將以淺顯易懂的方式進行說明，請務必閱讀至最後。
2. 什麼是質數？
質數的定義
質數是指「只能被 1 和它本身整除的自然數」。例如：2、3、5、7、11 是質數，但 4 和 6 則不是，因為它們可以被其他數字整除。
質數的具體例子與性質
讓我們看看一些前幾個質數：
- 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, …
質數具有以下幾個重要特性：
- 2 是唯一的偶數質數，其他質數皆為奇數。
- 質數在數字越大時出現頻率越低，但總數是無限的。
了解這些特性，有助於學習質數判斷的基礎知識。
3. 質數判斷的基本演算法
全數搜尋法（效率低的方法）
全數搜尋法是從 2 開始，檢查是否能被小於該數的所有整數整除。這種方法雖然簡單，但在處理較大的數字時效率極低。
全數搜尋法的 Python 範例程式碼
def is_prime_basic(n):
if n <= 1:
return False
for i in range(2, n):
if n % i == 0:
return False
return True
# 使用範例
print(is_prime_basic(11)) # 結果: True
print(is_prime_basic(15)) # 結果: False這段程式碼有助於理解基本的質數判斷邏輯。不過，由於處理大量數字時效率較差，實務上建議使用更高效的方法。
試除法（較高效的方法）
試除法只檢查從 2 到 √n 的整數是否能整除該數，能大幅減少不必要的計算。
試除法的 Python 範例程式碼
import math
def is_prime_optimized(n):
if n <= 1:
return False
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False
return True
# 使用範例
print(is_prime_optimized(17)) # 結果: True
print(is_prime_optimized(20)) # 結果: False相較於全數搜尋法，這個方法的計算量更少，特別適合用於較大的數字。
4. 使用埃拉托色尼篩法進行質數判斷
演算法概述
埃拉托色尼篩法是一種能有效找出某範圍內所有質數的演算法。基本概念如下：
- 建立一個包含 2 以上所有數字的清單。
- 取出第一個質數（2），刪除其所有倍數。
- 接著取出清單中下一個尚未刪除的最小數，重複相同的操作。
埃拉托色尼篩法的 Python 範例程式碼
def sieve_of_eratosthenes(limit):
primes = [True] * (limit + 1)
primes[0] = primes[1] = False # 0 和 1 不是質數
for i in range(2, int(limit ** 0.5) + 1):
if primes[i]:
for j in range(i * i, limit + 1, i):
primes[j] = False
return [x for x in range(limit + 1) if primes[x]]
# 使用範例
print(sieve_of_eratosthenes(30)) # 結果: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]埃拉托色尼篩法特別適合在一次需要找出大量質數時使用，效果非常出色。
5. 用 Python 實作質數判斷
基本實作
利用 Python 進行基本的質數判斷可以使用簡單的迴圈，這種方法適合初學者學習，但效率較低。
基本質數判斷的 Python 程式碼
def is_prime_basic(n):
if n <= 1:
return False
for i in range(2, n):
if n % i == 0:
return False
return True
# 使用範例
print(is_prime_basic(11)) # 結果: True
print(is_prime_basic(15)) # 結果: False這段程式碼可以幫助理解基本邏輯，但在處理大數時效率低，建議採用更優化的方式。
優化實作
使用試除法時，可將檢查範圍限制為 2 到 √n，使質數判斷更加快速。
優化後的 Python 程式碼範例
import math
def is_prime_optimized(n):
if n <= 1:
return False
if n <= 3: # 2 和 3 是質數
return True
if n % 2 == 0 or n % 3 == 0: # 能被 2 或 3 整除的數不是質數
return False
i = 5
while i * i <= n:
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6
return True
# 使用範例
print(is_prime_optimized(29)) # 結果: True
print(is_prime_optimized(49)) # 結果: False這種方法在處理大數時非常高效，適合實務應用。
6. 使用函式庫進行質數判斷
使用 SymPy 函式庫
SymPy 是一個專門用於數學計算的 Python 函式庫，其中包含了許多方便的質數判斷函數。其中之一是 isprime 函數，能夠輕鬆地判斷一個數是否為質數。
使用 SymPy 進行質數判斷的 Python 程式碼
from sympy import isprime
# 使用範例
print(isprime(13)) # 結果: True
print(isprime(16)) # 結果: False此外，透過 primerange 函數，可以取得指定範圍內所有的質數，並以清單的形式回傳。
取得範圍內質數的範例
from sympy import primerange
# 取得指定範圍內的質數
primes = list(primerange(10, 50))
print(primes) # 結果: [11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]使用 SymPy 可省去自行實作演算法的麻煩，是一個非常實用的工具。
7. 應用：處理大量質數的方法
處理大量資料的挑戰
當要處理非常大的數字或大量的質數時，計算量會大幅增加，因此必須使用高效的演算法或函式庫來應對。
透過平行處理加速
在 Python 中，可以使用平行處理技術加速埃拉托色尼篩法，使大量質數的判斷更加快速與高效。
使用平行處理進行質數判斷的範例
from concurrent.futures import ThreadPoolExecutor
def is_prime_threaded(n):
if n <= 1:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
def find_primes(limit):
with ThreadPoolExecutor() as executor:
results = list(executor.map(is_prime_threaded, range(2, limit)))
return [i for i, is_prime in enumerate(results, start=2) if is_prime]
# 使用範例
print(find_primes(50)) # 結果: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]這種方式在處理大量資料時效果非常顯著。
8. 常見問題（FAQ）
如何在 Python 中有效率地判斷質數？
想要高效地進行質數判斷，建議根據情況選擇以下方法：
- 處理小規模資料時：使用試除法
- 產生中等範圍內的質數列表時：使用埃拉托色尼篩法
- 處理大型數值時：使用 SymPy 的
isprime函數或平行處理
採用能兼顧效率的寫法，可以大幅提升程式的處理速度。
除了 SymPy，還有其他適合質數判斷的函式庫嗎？
除了 SymPy，以下函式庫也很實用：
- NumPy：適合處理大量數據，但本身不提供質數判斷功能。
- gmpy2：專為大數計算設計，能進行高效率的質數判斷。
根據不同的需求選擇合適的函式庫會更有效率。
應該使用埃拉托色尼篩法還是 SymPy？
建議根據使用場景做選擇：
- 若需要一次取得範圍內所有質數：適合使用埃拉托色尼篩法
- 若只需要判斷單一數值或處理極大數：使用 SymPy 較為方便
瞭解兩者的特點並適當使用，能讓質數判斷更加靈活與高效。
如何有效儲存質數判斷的結果？
若需儲存大量質數結果，以下方式相當實用：
- 儲存至資料庫：可使用 SQLite 或 PostgreSQL 等資料庫進行儲存與查詢。
- 輸出至檔案：可使用 CSV 或 JSON 格式，方便日後讀取使用。
以下是使用 Python 儲存的範例：
import json
# 將質數列表儲存為 JSON
primes = [2, 3, 5, 7, 11, 13]
with open('primes.json', 'w') as f:
json.dump(primes, f)
# 從 JSON 讀取
with open('primes.json', 'r') as f:
loaded_primes = json.load(f)
print(loaded_primes)9. 結語
本文介紹了使用 Python 進行質數判斷的各種方法，從基礎到進階應用。你應該已經學會以下重點：
- 質數的基本性質與定義
- 試除法與埃拉托色尼篩法等高效率演算法
- 活用 SymPy 函式庫與平行處理的進階技巧
- 實用的程式碼範例與資料儲存方法
質數判斷是學習演算法的核心主題之一。希望這篇文章能幫助你更深入理解 Python 程式設計。接下來可以挑戰更複雜的演算法或其他數學問題的應用！