最大公因數是能整除兩個整數的最大正整數。最經典的是歐幾里得演算法（輾轉相除法），時間複雜度 O(log min(a,b))，極為高效。
def gcd_recursive(a, b):
"""遞迴實作歐幾里得演算法"""
return a if b == 0 else gcd_recursive(b, a % b)
def gcd_iterative(a, b):
"""迭代實作，避免遞迴深度限制"""
while b:
a, b = b, a % b
return a
找出整數 x, y 使得 ax + by = gcd(a, b)，應用於模逆元計算：
def extended_gcd(a, b):
"""回傳 (gcd, x, y) 使得 ax + by = gcd"""
if b == 0:
return a, 1, 0
gcd, x1, y1 = extended_gcd(b, a % b)
x, y = y1, x1 - (a // b) * y1
return gcd, x, y
# 範例：求 3 模 11 的逆元
gcd, x, y = extended_gcd(3, 11)
print(f"3 * {x} + 11 * {y} = {gcd}") # 3 * 4 + 11 * (-1) = 1
print(f"3 的模 11 逆元為 {x % 11}") # 4
質數（Prime）是大於 1 且僅能被 1 與自身整除的正整數。
最直觀的方法，檢查 2 到 √n 的所有整數：
import math
def is_prime_trial(n):
"""試除法判斷質數，時間複雜度 O(√n)"""
if n < 2:
return False
if n == 2:
return True
if n % 2 == 0:
return False
for i in range(3, int(math.isqrt(n)) + 1, 2):
if n % i == 0:
return False
return True
大於 3 的質數皆為 6k±1 形式，減少 2/3 檢查次數：
def is_prime_optimized(n):
if n < 2:
return False
if n in (2, 3):
return True
if 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
決定性版本對 2^64 以下整數僅需測試特定基底：
import random
def is_prime_miller_rabin(n, k=10):
"""米勒-拉賓測試，k 為測試輪數，錯誤率 < 4^-k"""
if n < 2:
return False
small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
for p in small_primes:
if n % p == 0:
return n == p
# 將 n-1 分解為 d * 2^s
d, s = n - 1, 0
while d % 2 == 0:
d //= 2
s += 1
for _ in range(k):
a = random.randrange(2, n - 1)
x = pow(a, d, n)
if x == 1 or x == n - 1:
continue
for _ in range(s - 1):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False
return True
若需找出 N 以內所有質數，篩法效率最高 O(N log log N)：
def sieve_of_eratosthenes(limit):
"""回傳 limit 以內所有質數列表"""
is_prime = [True] * (limit + 1)
is_prime[0:2] = [False, False]
for i in range(2, int(limit**0.5) + 1):
if is_prime[i]:
for j in range(i*i, limit + 1, i):
is_prime[j] = False
return [i for i, prime in enumerate(is_prime) if prime]
primes = sieve_of_eratosthenes(100)
print(primes) # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
將整數分解為質數乘積，應用於密碼學、約數計算：
def prime_factors(n):
"""回傳質因數分解字典 {質數: 指數}"""
factors = {}
d = 2
while d * d <= n:
while n % d == 0:
factors[d] = factors.get(d, 0) + 1
n //= d
d += 1 if d == 2 else 2 # 2 之後只檢查奇數
if n > 1:
factors[n] = factors.get(n, 0) + 1
return factors
print(prime_factors(360)) # {2: 3, 3: 2, 5: 1} => 2^3 * 3^2 * 5
利用公式：LCM(a, b) = |a * b| / GCD(a, b)
def lcm(a, b):
return abs(a * b) // gcd_iterative(a, b)
# 多數 LCM
from functools import reduce
def lcm_multiple(*numbers):
return reduce(lcm, numbers)
print(lcm_multiple(12, 18, 24)) # 72
| 演算法 | 時間複雜度 | 適用範圍 | 備註 |
|---|---|---|---|
| 試除法 | O(√n) | n < 10^12 | 簡單、確定性 |
| 6k±1 優化 | O(√n/3) | n < 10^14 | 實務常用 |
| 米勒-拉賓 | O(k log³ n) | 任意大整數 | 概率性、極快 |
| 埃拉托斯特尼篩 | O(N log log N) | 批次求 N 內質數 | 空間 O(N) |
| 歐幾里得 GCD | O(log min(a,b)) | 任意大整數 | 極高效、確定性 |
import math
from math import gcd # Python 3.5+
from sympy import isprime, factorint # 第三方庫，功能更強大
print(gcd(48, 18)) # 6
print(math.isqrt(100)) # 10，Python 3.8+ 整數平方根
GCD 與質數判斷是數論基礎，廣泛應用於加密演算法（RSA）、雜湊函數、隨機數生成、競賽程式設計等領域。Python 內建 math.gcd 已高度優化，自行實作主要為教學與理解演算法原理。實務開發中，小數用試除法，大數用米勒-拉賓，批次求質數用篩法，質因數分解結合試除法與預先篩選質數表可達最佳效能。
