素数计算实战：从算法优化到Python实现

1次阅读

共计 1553 个字符，预计需要花费 4 分钟才能阅读完成。

素数在密码学中扮演着关键角色，特别是在 RSA 加密算法中，两个大素数的乘积构成了加密的基础。此外，在哈希表设计、随机数生成等领域也有重要应用。因此，高效计算素数不仅是一个有趣的数学问题，更具有实际工程意义。

暴力枚举法：对于每个数 n，检查 2 到 n - 1 是否能整除 n
时间复杂度：O(n²)
空间复杂度：O(1)
试除法优化：只需检查 2 到√n 的整数
时间复杂度：O(n√n)
空间复杂度：O(1)
埃拉托斯特尼筛法：通过标记倍数的方式筛选素数
时间复杂度：O(n log log n)
空间复杂度：O(n)

初始化一个布尔数组is_prime[0..n]，全部设为 True
将 0 和 1 标记为 False（非素数）
从 2 开始遍历到√n：
如果当前数字 p 是素数（即 is_prime[p] 为 True）
将所有 p 的倍数标记为非素数
收集所有仍标记为 True 的数字

def find_primes(m: int, n: int) -> tuple[list[int], int]:
    """
    使用埃拉托斯特尼筛法查找 m 到 n 之间的所有素数

    参数:
        m: 范围下限(包含)
        n: 范围上限(包含)

    返回:
        (素数列表, 素数个数)
    """
    if n < 2:
        return [], 0

    # 初始化筛子，注意 n + 1 确保包含 n 本身
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False

    # 筛法核心过程
    for p in range(2, int(n ** 0.5) + 1):
        if is_prime[p]:
            # 从 p * p 开始标记，因为更小的倍数已经被更小的素数标记过了
            for multiple in range(p * p, n + 1, p):
                is_prime[multiple] = False

    # 收集结果
    primes = [i for i in range(m, n + 1) if is_prime[i]]
    return primes, len(primes)

筛法的时间复杂度为 O(n log log n)，这是因为：

对于每个素数 p，我们需要标记 n / p 个倍数。总操作次数约为：

$$
\sum_{p\leq n, p\text{是素数}} \frac{n}{p} \approx n \sum_{p\leq n} \frac{1}{p} \approx n \log \log n
$$

n 值	时间(秒)
10^5	0.03
10^6	0.3
10^7	3.5

使用 bitmap：每个布尔值占 1 字节，可以用位运算压缩到 1 位
分段筛法：处理超大范围时，可将范围分成小块处理

# 使用 bitarray 库的示例
from bitarray import bitarray

def sieve_bitarray(n):
    """使用 bitarray 优化内存的筛法实现"""
    is_prime = bitarray(n + 1)
    is_prime.setall(True)
    is_prime[0] = is_prime[1] = False

    for p in range(2, int(n ** 0.5) + 1):
        if is_prime[p]:
            is_prime[p*p::p] = False

    return is_prime