统计素数的常用方法详解

1. 什么是素数？

素数（质数） 是大于 1 的自然数，只能被 1 和它本身整除。

示例：

• 素数：2, 3, 5, 7, 11, ...
• 非素数：4, 6, 8, 9, ...

---

2. 最基础的解法：逐个判断

思路

对每个数 m，检查是否能被 2 到 m-1 之间的数整除。如果都不能，则是素数。

示例代码

python
def is_prime(m):
    if m <= 1:
        return False
    for i in range(2, m):
        if m % i == 0:
            return False
    return True

def count_primes(n):
    count = 0
    for i in range(2, n+1):
        if is_prime(i):
            count += 1
    return count

缺点

效率极低，例如判断 100 是否为素数要检查 98 次，当 n 很大时（如 10⁶），计算会非常慢。

---

3. 优化 1：只检查到平方根

原理

如果 m 能被某个数整除，那么其中一个因数一定小于等于 √m。例如 16 的因数 4，只需要检查到 4 即可。

示例代码

python
import math

def is_prime(m):
    if m <= 1:
        return False
    if m == 2:    # 2 是唯一的偶素数
        return True
    if m % 2 == 0:  # 其他偶数直接排除
        return False
    sqrt_m = int(math.sqrt(m)) + 1  # 检查到平方根
    for i in range(3, sqrt_m, 2):   # 只检查奇数
        if m % i == 0:
            return False
    return True

改进点

• 跳过偶数（除了 2）
• 只检查到平方根
• 时间复杂度降为 O(√n)

---

4. 优化 2：埃拉托斯特尼筛法（Sieve of Eratosthenes）

原理

通过“筛子”筛掉非素数，剩下的就是素数：

1. 先标记 0 和 1 不是素数。
2. 从 2 开始，标记所有 2 的倍数。
3. 下一个未被标记的数是 3，标记所有 3 的倍数。
4. 重复直到 √n，剩下的未被标记的就是素数。

示例代码

python
def count_primes_sieve(n):
    if n < 2:
        return 0
    sieve = [True] * (n+1)  # 初始化为全 True
    sieve[0] = sieve[1] = False  # 0 和 1 不是素数
    for i in range(2, int(math.sqrt(n)) + 1):
        if sieve[i]:  # 如果 i 是素数
            sieve[i*i : n+1 : i] = [False] * len(sieve[i*i : n+1 : i])  # 标记 i 的倍数
    return sum(sieve)  # 统计 True 的数量

优势

时间复杂度为 O(n log log n)，处理 n=10^6 仅需几毫秒。

---

5. 筛法进一步优化（跳过偶数）

原理

除了 2，所有偶数都不是素数。初始化时直接排除偶数，节省一半空间和时间。

示例代码

python
def count_primes_sieve_optimized(n):
    if n < 2:
        return 0
    if n == 2:
        return 1
    sieve = [True] * (n+1)
    sieve[0] = sieve[1] = False
    sieve[4::2] = [False] * ((n-4)//2 + 1)  # 标记所有偶数（除了2）
    sieve[2] = True  # 2 是素数
    for i in range(3, int(math.sqrt(n)) + 1, 2):  # 只检查奇数
        if sieve[i]:
            sieve[i*i : n+1 : 2*i] = [False] * len(sieve[i*i : n+1 : 2*i])  # 步长设为 2i
    return sum(sieve)

改进点

• 减少了一半的标记操作
• 更高效地利用内存

---

6. 性能对比

方法	特点	时间复杂度
基础方法	简单直观，效率低下	O(n√n)
平方根判断法	效率提升明显	O(n√n)
埃氏筛法	快速高效	O(n log log n)
优化筛法（跳偶）	空间与时间更优	O(n log log n)

测试代码

python
import time

n = 100000

start = time.time()
print(count_primes_sieve(n))
print("筛法耗时:", time.time() - start)

start = time.time()
print(count_primes(n))  # 基础方法（逐个判断）
print("基础方法耗时:", time.time() - start)

---

7. 总结

• 小数据量（n < 10⁴）：可以用逐个判断法，简单直观。
• 大数据量（n ≥ 10⁵）：必须使用筛法，速度差可达数百倍。
• 极端情况（n ≈ 10⁸）：可以考虑使用位运算（如 bitarray）来节省内存。