高效求解指定范围内的素数：从算法优化到Python实现

1次阅读

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

素数（质数）在密码学、哈希算法、随机数生成等领域有广泛应用。在算法竞赛中，素数判断和筛选是常见的基础题型。本文将以 Python 为例，探讨如何高效求解 [m, n] 范围内的所有素数。

最直观的方法是逐个判断区间内的每个数是否为素数：

def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num**0.5)+1):
        if num % i == 0:
            return False
    return True

def prime_range_naive(m, n):
    primes = []
    for num in range(m, n+1):
        if is_prime(num):
            primes.append(num)
    return primes

时间复杂度：O(n√n)
缺点：当 n 较大时（如 n >1e6），性能急剧下降

初始化一个布尔数组is_prime[0..n]，初始全为 True
从 p = 2 开始，将 p 的倍数标记为非素数
重复步骤 2 直到 p² > n
最后保留标记为 True 的索引即为素数

def sieve_of_eratosthenes(n):
    is_prime = [True] * (n+1)
    is_prime[0:2] = [False, False]  # 0 和 1 不是素数

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

    return [i for i, prime in enumerate(is_prime) if prime]

def prime_range_sieve(m, n):
    primes = sieve_of_eratosthenes(n)
    return [p for p in primes if p >= m]

时间复杂度：O(n log log n)
空间复杂度：O(n)

算法类型	n=1e4 耗时	n=1e5 耗时	n=1e6 耗时
暴力法	15ms	380ms	9.2s
筛法	2ms	12ms	140ms

当 n >1e7 时，常规筛法可能内存不足。解决方案：

先用筛法求出√n 以内的素数
将 [m,n] 区间分为多个小段
用已知的小素数筛选每个小段

def segmented_sieve(m, n):
    limit = int(n**0.5) + 1
    base_primes = sieve_of_eratosthenes(limit)

    primes = []
    size = n - m + 1
    is_prime = [True] * size

    for p in base_primes:
        start = max(p*p, ((m + p - 1) // p) * p)
        for multiple in range(start, n+1, p):
            is_prime[multiple - m] = False

    for i in range(size):
        if is_prime[i] and (i + m) >= 2:
            primes.append(i + m)

    return primes

用 1bit 代替 1byte 存储布尔值：

import array

def sieve_bit(n):
    size = (n + 1) // 2  # 只存储奇数
    sieve = array.array('B', [1]) * size

    for i in range(1, int(n**0.5) // 2 + 1):
        if sieve[i]:
            step = 2*i + 1
            sieve[i*i*2::step] = array.array('B', [0]) * len(sieve[i*i*2::step])

    primes = [2] if n >= 2 else []
    primes += [2*i+1 for i in range(1, size) if sieve[i]]
    return primes

边界处理：特别注意 m = 1 时的情况（1 不是素数）
重复筛选 ：筛法应从 p²开始标记倍数（p*(p-1) 已被更小的素数处理过）
并行化：分段筛法天然适合并行处理不同区间

import time
import math

def main():
    m, n = map(int, input("请输入范围 m n:").split())

    start = time.time()
    primes = segmented_sieve(m, n)
    elapsed = time.time() - start

    print("素数列表:", " ".join(map(str, primes)))
    print(f"共找到 {len(primes)} 个素数，耗时 {elapsed:.4f} 秒")

if __name__ == "__main__":
    main()

当 n >1e9 时，如何优化筛法？可以考虑：