### Python 中 `is_prime` 函数的实现与用法 在 Python 中，`is_prime` 函数用于判断一个整数是否为质数。以下是几种常见的实现方式及其解释。 #### 1. 基于简单迭代的实现 一种基本的方法是通过从 2 到该数的平方根进行迭代检查，判断是否存在任何因子[^5]。 ```python def is_prime(n): if n <= 1: return False if n <= 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 ``` 此方法利用了所有质数（大于 3 的）都可以表示为 6k ± 1 的性质，从而减少不必要的检查次数[^5]。 #### 2. 使用 SymPy 库的实现 Python 的 SymPy 库提供了一个内置函数 `isprime`，可以高效地判断一个数是否为质数。 ```python from sympy import isprime print(isprime(11)) # 输出: True print(isprime(15)) # 输出: False ``` SymPy 的 `isprime` 函数基于 Miller-Rabin 素性测试算法，适用于大整数的素性检测[^6]。 #### 3. 基于 Miller-Rabin 算法的实现 Miller-Rabin 算法是一种概率性的素性测试方法，能够高效判断大整数是否为质数。 ```python import random def miller_rabin(n, k=5): # k 是测试轮数 if n <= 1: return False if n <= 3: return True if n % 2 == 0: return False # 将 n-1 表示为 2^r * d 的形式 r, d = 0, n - 1 while d % 2 == 0: d //= 2 r += 1 def witness(a): x = pow(a, d, n) if x == 1 or x == n - 1: return False for _ in range(r - 1): x = pow(x, 2, n) if x == n - 1: return False return True for _ in range(k): a = random.randint(2, n - 2) if witness(a): return False return True ``` 此实现中，`witness` 函数用于检测随机选择的基数 `a` 是否为合数的见证者。经过多轮测试后，如果未发现任何见证者，则认为该数可能是质数[^7]。 #### 4. 使用生成器的实现 可以使用生成器来生成一系列质数，并通过比较判断目标数是否为质数。 ```python def gen_primes(): D = {} q = 2 while True: if q not in D: yield q D[q * q] = [q] else: for p in D[q]: D.setdefault(p + q, []).append(p) del D[q] q += 1 def is_prime_gen(n): primes = gen_primes() prime = next(primes) while prime <= n: if prime == n: return True prime = next(primes) return False ``` 上述代码中，`gen_primes` 是一个生成器函数，能够按需生成质数序列。`is_prime_gen` 函数通过逐个比较生成的质数，判断目标数是否为质数[^8]。 ### 注意事项 在实际应用中，选择合适的实现方式取决于具体需求。对于小范围的素性检测，简单的迭代方法即可满足需求；而对于大整数或高性能要求的场景，建议使用 SymPy 或自定义的 Miller-Rabin 算法实现[^9]。