如何用Python编写一个判断质数的函数

判断质数是计算机科学中的一个基本问题。在 Python 中编写一个判断质数的函数并不困难，需要遵循几个基本策略。

1. 筛法

筛法是一种常见的判断质数的算法。其基本思路是：将所有小于等于 n 的正整数分成两组，一个是质数组，一个是合数组，然后不断筛选，最终剩下的就是质数。

2. 费马检验

费马检验是一种简单的判断质数的算法。其基于两个数学定理：

? 费马小定理：如果 p 是质数，则对于任意整数 a，a^{p-1} ≡ 1 (mod p)。

? 威特尼克定理：如果 n 是奇合数，则存在正整数 a，使得 a^{n-1} ≡ 1 (mod n)，且 a^{\frac{n-1}{r}}

eq 1 (mod n) 对所有的 r 是质因数成立。

3. 暴力枚举

暴力枚举是最简单的判断质数的算法，其基本思路是：对于每个小于等于 n 的正整数 i，如果 n 能被 i 整除且 i 不等于 1 和 n，则 n 是合数，否则是质数。

下面我们来具体介绍如何用 Python 实现这三种算法。

1. 筛法实现质数判断函数：

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

在这个函数中，使用了一个 sieve 数组来标记小于等于 n 的正整数是否为质数。当 n 很大时，这个函数的效率可能比较低，因为我们需要分配一个很大的数组。如果只需要判断一个数是否为质数，可以将这个函数改成一个生成器，这样可以降低空间复杂度：

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

2. 费马检验实现质数判断函数：

import random

def mod_pow(a, b, p):
    res = 1
    while b > 0:
        if b & 1 == 1:
            res = res * a % p
        a = a * a % p
        b //= 2
    return res

def is_prime(n, rounds=5):
    if n <= 1:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    for i in range(rounds):
        a = random.randint(2, n-2)
        if mod_pow(a, n-1, n) != 1:
            return False
    return True

这个函数使用了一个辅助函数 mod_pow 来计算 a 的 b 次方模 p 的结果。在主函数中，使用了 rounds 次随机测试来判断 n 是否是质数。随机测试的次数越多，判断结果越准确。

3. 暴力枚举实现质数判断函数：

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

该函数的时间复杂度为 O(\sqrt n)，空间复杂度为 O(1)。这个函数不适合用于判断很大的质数。

总之，使用 Python 实现一个判断质数的函数并不难，只需要掌握上述三种基本算法即可。在实际应用中，需要根据具体需求选择不同的算法。如果需要判断很大的质数，可以考虑使用更高级的算法。