1. 问题背景与理解

第一次看到"非素数个数"这个题目时，我正坐在厦门大学计算机实验室里准备机试练习。作为一道经典的算法题，它看似简单却暗藏玄机。题目要求我们统计给定区间内非素数的数量，这比直接判断素数要绕一个弯子。

素数（质数）是指大于1的自然数中，除了1和它本身外没有其他因数的数。而非素数就是除了素数以外的所有自然数，包括1和合数（即可以分解为多个素数乘积的数）。这道题的关键在于如何高效地判断一个数是否为素数，然后取反统计。

2. 素数判断的常见方法

2.1 暴力枚举法

最直观的方法是暴力枚举：对于一个数n，检查2到n-1之间是否有能整除n的数。如果有，则n不是素数。

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

这种方法的时间复杂度是O(n)，对于大数来说效率极低。在机试环境下，当n很大时（比如10^6），这种算法会严重超时。

2.2 优化到平方根

一个重要的数学观察是：如果n不是素数，那么它至少有一个因数小于等于√n。因此我们只需要检查到√n即可：

import math def is_prime(n): if n <= 1: return False for i in range(2, int(math.sqrt(n)) + 1): if n % i == 0: return False return True

这样时间复杂度降到了O(√n)，效率提升显著。这也是面试中最常被问到的素数判断方法。

3. 埃拉托斯特尼筛法（筛法）

3.1 筛法原理

当需要统计一个区间内非素数的数量时，逐个判断每个数是否为素数仍然不够高效。埃拉托斯特尼筛法（Sieve of Eratosthenes）是更优的选择。

筛法的核心思想是：从2开始，将每个素数的倍数都标记为非素数。这样当我们处理完所有小于等于√n的数后，剩下的未被标记的数就是素数。

3.2 筛法实现

def count_non_primes(n): if n < 2: return n is_prime = [True] * (n + 1) is_prime[0] = is_prime[1] = False for i in range(2, int(math.sqrt(n)) + 1): if is_prime[i]: for j in range(i*i, n+1, i): is_prime[j] = False return n + 1 - sum(is_prime)

这个算法的时间复杂度是O(n log log n)，空间复杂度是O(n)。对于n=10^6的情况，筛法比逐个判断快约100倍。

4. 区间非素数统计

4.1 问题变种

原题可能要求统计[a, b]区间内的非素数数量，而不仅仅是[1, n]。这时我们可以：

1. 使用筛法生成1到b的所有素数标记
2. 统计a到b区间内的非素数数量

def count_non_primes_in_range(a, b): if b < 2: return b - a + 1 is_prime = [True] * (b + 1) is_prime[0] = is_prime[1] = False for i in range(2, int(math.sqrt(b)) + 1): if is_prime[i]: for j in range(i*i, b+1, i): is_prime[j] = False return sum(1 for x in range(a, b+1) if not is_prime[x])

4.2 边界情况处理

在实际编程中，需要特别注意边界情况：

• a < 2时的处理
• a > b时的处理
• 大数情况下的内存优化

5. 性能优化技巧

5.1 分段筛法

当区间很大时（比如a=1, b=10^9），传统的筛法会消耗过多内存。这时可以使用分段筛法：

1. 先用筛法生成小素数（如≤√b）
2. 然后将大区间分成若干段，用这些小素数筛选每段

5.2 位压缩存储

为了节省空间，可以用位运算来存储素数标记数组。Python中可以使用bytearray：

is_prime = bytearray([1]) * (n + 1) is_prime[0] = is_prime[1] = 0

这样可以将内存使用减少到原来的1/8。

6. 实际测试与验证

为了验证我们的算法正确性，可以编写测试用例：

test_cases = [ (1, 10, 6), # 非素数：1,4,6,8,9,10 (10, 20, 9), # 非素数：10,12,14,15,16,18,20 (100, 200, 78), (1000000, 1001000, 920) ] for a, b, expected in test_cases: assert count_non_primes_in_range(a, b) == expected

7. 常见错误与调试

在实现过程中，我遇到过几个典型错误：

1. 边界条件错误：忘记处理n=0或1的情况
2. 循环范围错误：筛法内层循环应该从ii开始，而不是i2
3. 数据类型溢出：在C++等语言中，i*i可能导致整数溢出
4. 性能陷阱：在Python中，sum(is_prime)比循环计数快很多

调试时可以打印中间结果，比如小范围内的素数标记数组，验证筛选是否正确。

8. 算法选择建议

根据不同的输入规模，建议采用不同的策略：

1. 小范围查询（n≤10^6）：直接使用筛法预处理
2. 大范围单次查询：使用优化的试除法（如Miller-Rabin素性测试）
3. 超大范围区间查询：分段筛法

在编程竞赛中，通常n≤10^7，因此标准筛法是最实用的选择。

9. 扩展思考

这个问题可以延伸出许多有趣的变种：

1. 统计半素数（两个素数乘积）的数量
2. 找出最长的连续合数区间
3. 计算素数的密度函数
4. 研究素数分布的规律

理解素数判断和筛法不仅是解决这道题的关键，也是许多数论问题的基础。我在准备ACM竞赛时，这类题目帮助我深入理解了算法优化的思维方式。