在 Python 中高效统计给定范围内的素数数量，通常可以采用 **埃拉托斯特尼筛法（Sieve of Eratosthenes）** 或 **分段筛法（Segmented Sieve）**。这些方法在时间复杂度和空间复杂度上都优于直接遍历并判断每个数是否为素数的传统方式。 ### 使用埃拉托斯特尼筛法统计素数 埃拉托斯特尼筛法是一种经典的筛选素数的方法，适用于统计小于等于 $ B $ 的所有素数。通过构造一个布尔数组 `sieve`，将非素数标记为 `False`，最后统计范围 $[A, B]$ 内的素数数量。 ```python def count_primes_in_range(A, B): if B < 2: return 0 sieve = [True] * (B + 1) sieve[0] = sieve[1] = False for i in range(2, int(B**0.5) + 1): if sieve[i]: for j in range(i * i, B + 1, i): sieve[j] = False return sum(1 for x in range(A, B + 1) if sieve[x]) ``` 该方法的时间复杂度为 $ O(n \log(\log(n))) $，适用于 $ B \leq 10^6 $ 的情况。如果 $ A $ 和 $ B $ 的范围较大，可以进一步优化内存使用，例如只保留当前筛选所需的区间段[^1]。 ### 使用分段筛法统计素数 当 $ A $ 和 $ B $ 的范围非常大（例如 $ B $ 达到 $ 10^9 $），使用分段筛法更为高效。该方法首先用埃拉托斯特尼筛法生成小于等于 $ \sqrt{B} $ 的素数，然后将区间 $[A, B]$ 划分为多个小块，依次筛除非素数。 ```python import math def segmented_sieve(A, B): limit = int(math.sqrt(B)) + 1 base_primes = [] sieve = [True] * limit sieve[0] = sieve[1] = False for i in range(2, limit): if sieve[i]: base_primes.append(i) for j in range(i * i, limit, i): sieve[j] = False size = B - A + 1 is_prime = [True] * size for p in base_primes: start = max(p * p, ((A + p - 1) // p) * p) for j in range(start, B + 1, p): is_prime[j - A] = False if A == 0: is_prime[0] = False if A <= 1: is_prime[1 - A] = False return sum(is_prime) ``` 该方法在处理大规模区间时具有良好的内存效率和计算性能，适用于 $ A $ 和 $ B $ 都非常大的场景[^3]。 ### 使用数学库简化实现 在实际开发中，也可以借助 Python 的数学库如 `SymPy` 来快速实现素数统计。例如： ```python from sympy import primerange def count_primes_with_sympy(A, B): return len(list(primerange(A, B + 1))) ``` 该方法代码简洁，适合快速原型开发，但性能略逊于手动实现的筛法[^4]。